Cracking The Coding Interview Together – Problem 10.5: Sparse Search

Picture this: you are building a lightning-fast autocomplete feature for a legacy documentation system. Your data store hands you a sorted array of strings, but due to historical data corruption or dynamic deletions, the array is heavily interspersed with empty strings. Your users expect sub-millisecond search times, but a naive linear scan over millions of elements is completely off the table. How do we adapt our most trusted searching algorithm when the data structure has built-in gaps?

If we try to apply a standard binary search blindly, we immediately hit a wall of empty strings where our midpoints land, completely invalidating our standard greater-than or less-than comparisons. In this edition of The Dev Learnings, we are going to unpack Problem 10.5 from Cracking the Coding Interview and build a robust, production-ready modified binary search algorithm together.

Problem Statement

Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string. Our operational goals are:

• Input: A String[] array containing sorted non-empty strings and potentially many empty strings (""), and a target String to find.
• Output: The integer index of the target string if present; otherwise, return -1.
• Constraint: Optimize our search time complexity far beyond the linear $O(N)$ worst-case scan.

Analyze the Problem Together

Let's break down the constraints and hunt for the "Aha!" conflict. In a classic binary search, we look at the midpoint element, compare it directly to our target, and decide whether to discard the left or the right half. But what happens when array[mid] is an empty string?

We cannot tell whether our target belongs to the left half or the right half based on an empty string alone. The "Aha!" moment occurs when we realize that while mid might land on an empty string, we can simply "walk" outward from mid—to the left and to the right—until we find the nearest non-empty string. Once we locate a non-empty string closest to our original midpoint, we establish a valid reference point to compare against our target string.

Let's compare our options:

We choose the Modified Binary Search because it respects our memory constraints while drastically reducing search times.

Questions for the Interviewer

Before we write a single line of code, as senior engineers, we must clarify the operational boundaries:

1. Case Sensitivity: Are the string comparisons case-sensitive, or should we normalize them using compareToIgnoreCase?
2. Density of Empties: What is the expected distribution of empty strings? If the array is 99% empty strings, could our outward scan degrade to linear time frequently?
3. Null Safety: Can the array itself or the target string be null, or are empty strings strictly represented as ""?
4. Duplicate Entries: If there are duplicate target strings, does any valid index suffice, or do we need the first/last occurrence?

Think About the Solution

Our solution revolves around a recursive or iterative helper method that performs binary search with a smart midpoint adjustment step. Let's trace our execution flow:

1. Initialize pointers: low = 0 and high = array.length - 1.
2. While low <= high:
   • Calculate standard midpoint: mid = low + (high - low) / 2.
   • If array[mid] is empty, initialize two temporary pointers, left = mid - 1 and right = mid + 1, and scan outward until we find a non-empty string or cross our bounds.
   • If both outward scans fail to find a non-empty string, the entire sub-array in this range is empty; we can safely return -1.
   • Once we have our closest non-empty string (let's say at index mid), compare it with the target using compareTo.
   • Adjust low and high accordingly based on standard lexicographical ordering.

Write Code and Explain

Here is our production-ready Java implementation for the Sparse Search problem:

public class SparseSearch {

    public static int search(String[] strings, String target) {
        if (strings == null || target == null || target.isEmpty()) {
            return -1;
        }
        return search(strings, target, 0, strings.length - 1);
    }

    private static int search(String[] strings, String target, int low, int high) {
        if (low > high) {
            return -1;
        }

        // Compute the standard midpoint
        int mid = low + (high - low) / 2;

        // If mid points to an empty string, find the closest non-empty string
        if (strings[mid].isEmpty()) {
            int left = mid - 1;
            int right = mid + 1;

            while (true) {
                if (left < low && right > high) {
                    // We searched outward across the entire active range and found only blanks
                    return -1;
                } else if (right <= high && !strings[right].isEmpty()) {
                    mid = right;
                    break;
                } else if (left >= low && !strings[left].isEmpty()) {
                    mid = left;
                    break;
                }
                right++;
                left--;
            }
        }

        // Now mid points to a valid non-empty string; compare with target
        int res = target.compareTo(strings[mid]);

        if (res == 0) {
            return mid;
        } else if (res < target.length() * 0 ? ... : res < 0) { // standard string comparison
            // Target is smaller, search left half
            return search(strings, target, low, mid - 1);
        } else {
            // Target is larger, search right half
            return search(strings, target, mid + 1, high);
        }
    }
}

Let's walk through the code step-by-step:

• Validation Guard: We instantly reject null arrays or empty targets to prevent runtime exceptions.
• Outward Scanning Logic: When strings[mid].isEmpty() evaluates to true, we deploy left and right pointers. By incrementing and decrementing them simultaneously in a single loop, we efficiently locate the nearest non-empty neighbor without unnecessary iterations.
• Lexicographical Comparison: Java's String.compareTo() handles alphabetical ordering. If res == 0, we found our exact match and return the adjusted index.

Time & Space Complexity

• Time Complexity:
  • Average Case: $O(\log N)$. In well-distributed datasets, our outward scan resolves almost instantly, preserving standard binary search performance.
  • Worst Case: $O(N)$. If the array consists entirely of empty strings except for a single entry at the end, our outward search devolves into a linear scan.
• Space Complexity: $O(\log N)$ auxiliary stack space for recursive calls in the average case (or $O(1)$ if refactored into an iterative loop). We allocate no additional heap structures.

Why This Problem Matters (The Senior Perspective)

Sparse Search is a fantastic lesson in algorithm adaptation. In real-world backend engineering, you rarely receive pristine data directly from a database. Legacy migrations, sparse matrix representations in machine learning, and nullable columnar data stores frequently present us with datasets riddled with placeholder or null values.

Knowing how to gracefully pivot standard algorithmic patterns—like augmenting binary search with linear probing steps—separates engineers who only memorize textbook solutions from those who can architect resilient solutions for messy, real-world data constraints.

Final Thoughts

Mastering algorithms like Sparse Search builds your intuition for edge-case handling and performance tuning. Try refactoring the recursive implementation above into an iterative loop to eliminate stack-overflow risks on extremely deep recursive trees. Happy coding, and keep building robust systems!