The O(n) Club: Shortest Distance to a Character — Why Single Pass Devs Cry Twice

The O(n) Club: Shortest Distance to a Character — Why Single Pass Devs Cry Twice

⚡ TL;DR

You want the minimum distance from every index in a string to the closest target character, and you want it fast—without off-by-one-induced despair. Brute force is for people who like slow tests. Here’s the O(n) adult version:

// Java snippet
String s = "teachercat";
char c = 'c';
int[] res = new int[s.length()];
// Two-passes: left-to-right and right-to-left like a laser pointer with commitment.

🧠 How Devs Usually Mess This Up

Most devs leap in with a single left-to-right pass, then wonder why edge cases come back haunted. They forget that just like cats, the target character can appear on either side. Plus, if you forget to properly set your infinity values or rely on zeros, your output will be more random than your caffeine intake on sprint week. Always use Math.abs() and only trust Integer.MAX_VALUE—never your gut.

🔍 What’s Actually Going On

Picture your string as a very needy robot on a one-way street. The robot records how far every position is from the last time it saw its target character walking by (left to right pass). But just when you think you’re done, turns out the character can sneak up from the right too—yep, you need another pass in the other direction. Both passes, then min distance for each spot. Clean, predictable, no caffeine required.

🛠️ PseudoCode

• Initialize: Distance array with fake ‘infinity’ (a very large number, a.k.a. Java’s existential dread).

  int[] res = new int[s.length()];
  Arrays.fill(res, Integer.MAX_VALUE);

• First Pass (Left to Right): Keep track of last-seen c. Set distance to zero if found, otherwise update with distance from last c.

  int prev = -1;
  for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == c) prev = i;
      if (prev != -1) res[i] = i - prev;
  }

• Second Pass (Right to Left): Repeat above logic, but backwards. Update result with minimum of current and new distance.

  prev = -1;
  for (int i = s.length() - 1; i >= 0; i--) {
      if (s.charAt(i) == c) prev = i;
      if (prev != -1) res[i] = Math.min(res[i], prev - i);
  }

💻 The Code

public int[] shortestToChar(String s, char c) {
    int n = s.length();
    int[] res = new int[n];
    int prev = -1;
     // First pass: left to right
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == c) {
            prev = i;
        }
        if (prev == -1) {
            res[i] = Integer.MAX_VALUE / 2;
        } else {
            res[i] = i - prev;
        }
    }
     // Second pass: right to left
    prev = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (s.charAt(i) == c) {
            prev = i;
        }
        if (prev != -1) {
            res[i] = Math.min(res[i], Math.abs(prev - i));
        }
    }
    return res;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Infinity Misfires: Using 0 or something else as initial value. Just don’t. Signed, every broken test case.
• Single Pass Syndrome: Closest character can be on the right. Don’t lazily assume otherwise.
• Edge Cases: Your leftmost and rightmost markers had better be handled, or your interviewer will notice.
• Complexity: O(n) time, O(n) space. Use it in a text editor, genome analyzer, or just to impress date night.

🧠 Interviewer Brain-Tattoo

“Two sweeps find the closest, just like code reviews. Never trust only one look.”