821. Shortest Distance to a Character

EasyView on LeetCode

Array Hash Table String

Time: O(n)

Space: O(n)

Intuition

Two-pass: first scan left-to-right tracking last seen c position; then right-to-left. Take minimum.

Algorithm

1Pass 1 (L→R): for each i, distance[i] = i - last_c_position (∞ if not seen yet).
2Pass 2 (R→L): for each i from right, distance[i] = min(distance[i], next_c_position - i).

Common Pitfalls

•Initialize last_c_position as -infinity (or a very negative number) in pass 1 to handle positions before the first c.

821.cs

// Approach: Two-pass L→R then R→L; each position stores distance to the nearest target character; final answer takes the minimum.
// Time: O(n) Space: O(n)

public class Solution
{
    public int[] ShortestToChar(string s, char c)
    {
        int n = s.Length;
        int[] ans = new int[n];
        int prev = -n;

        for (int i = 0; i < n; ++i)
        {
            if (s[i] == c)
                prev = i;
            ans[i] = i - prev;
        }

        for (int i = prev - 1; i >= 0; --i)
        {
            if (s[i] == c)
                prev = i;
            ans[i] = Math.Min(ans[i], prev - i);
        }

        return ans;
    }
}

Was this solution helpful?