Shortest Distance to a Character: Two-Pass Array Sweep

LeetCode 821, Shortest Distance to a Character, gives you a string s and a character c that is guaranteed to appear at least once in s. Your job is to return an array of integers where each entry is the shortest distance from that position to any occurrence of c in the string.

For example, given s = "loveleetcode" and c = "e", the output is [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]. Index 0 ('l') is 3 positions away from the nearest 'e' at index 3. Index 3 is an 'e' itself, so the distance is 0.

Why this problem matters

This problem is a clean introduction to the bidirectional sweep pattern. Many array problems look like they require checking every pair of elements (O(n^2)), but can be solved in O(n) by making two passes: one forward and one backward. You gather partial information from one direction, then complete it from the other.

Once you internalize this two-pass technique here, you will recognize it immediately in problems like Candy (LeetCode 135), Trapping Rain Water (LeetCode 42), and Product of Array Except Self (LeetCode 238). It is a small idea with broad reach.

The key insight

Looking at any single position, the nearest target character is either to its left or to its right. You cannot know which side is closer without checking both. A brute force approach would scan left and right from every position, but that is O(n^2).

The trick is to split the work into two linear passes. In the left-to-right pass, you track how far each position is from the last c you saw on the left. In the right-to-left pass, you track how far each position is from the next c you will see on the right. Taking the minimum of both passes gives you the true shortest distance.

The approach

1. Create a result array of size n, initialized to infinity (or a large number).
2. Left-to-right pass: Walk through the string. Whenever you hit c, record its index as prev. For each position, if prev is valid, set result[i] = i - prev.
3. Right-to-left pass: Walk backward. Whenever you hit c, record its index as prev. For each position, set result[i] = min(result[i], prev - i).

After both passes, every position holds the shortest distance to the nearest c in either direction.

def shortestToChar(s, c):
    n = len(s)
    result = [float('inf')] * n

    prev = float('-inf')
    for i in range(n):
        if s[i] == c:
            prev = i
        result[i] = i - prev

    prev = float('inf')
    for i in range(n - 1, -1, -1):
        if s[i] == c:
            prev = i
        result[i] = min(result[i], prev - i)

    return result

Visual walkthrough

Let's trace through s = "loveleetcode" and c = "e" step by step. Watch how the left-to-right pass handles everything after the first 'e', and the right-to-left pass fills in the positions that come before it.

The two passes complement each other perfectly. The forward pass leaves positions before the first 'e' at infinity because it has not seen a target yet. The backward pass fixes those positions because it approaches them from the right side where an 'e' has already been found.

Complexity analysis

Time: Two passes through the string, each doing constant work per character. Total: O(n).

Space: The result array is O(n). This is required by the problem, so it is the minimum possible. The only extra variables are prev and loop counters.

The building blocks

Bidirectional sweep

The core technique is making two passes in opposite directions. Each pass captures distance information from one side. The final answer at each position is the minimum of both passes. This pattern works whenever the answer at a position depends on the nearest occurrence of something, and that occurrence could be on either side.

You will see this same structure in:

• Candy (LeetCode 135), where you assign values based on neighbors on both sides.
• Product of Array Except Self (LeetCode 238), where prefix and suffix products are combined.

Lazy initialization with infinity

Instead of special-casing "no target character seen yet," you initialize distances to infinity and let the math handle it naturally. When prev starts at negative infinity, i - prev evaluates to a very large number, which gets corrected in the second pass. This avoids messy conditionals and keeps the loop body clean.

Edge cases

Single character string: s = "e", c = "e". The string has one character that matches. Result: [0].

Target only at the end: s = "aaae", c = "e". The left-to-right pass leaves indices 0, 1, 2 at large values. The right-to-left pass corrects them to [3, 2, 1, 0].

Target only at the start: s = "eaaa", c = "e". The left-to-right pass handles everything: [0, 1, 2, 3]. The right-to-left pass does not improve any value.

Every character is the target: s = "eee", c = "e". Every distance is 0. Result: [0, 0, 0].

Two targets far apart: s = "exxxxe", c = "e". The middle positions get their distance from whichever 'e' is closer. Result: [0, 1, 2, 2, 1, 0].

From understanding to recall

The algorithm is two short loops with a tracking variable. It is easy to read, but reproducing it from scratch under pressure requires knowing exactly when to update prev and which direction gives i - prev versus prev - i. These small details are where people trip up in interviews.

Write the solution on a blank screen. Do it again in a few days. Then again next week. After a few repetitions with increasing intervals, the two-pass structure becomes automatic. You stop reconstructing the logic and start just writing it. That is the difference between understanding and fluency.

Related posts

• Move Zeroes - Another in-place array technique using a clean single-pass pointer strategy
• Find All Numbers Disappeared in an Array - Uses the array itself as a data structure with the index-marking pattern
• Next Greater Element I - A different approach to finding nearest elements using a monotonic stack