Five Coding Interview Problems Where Your First Solution Isn't Optimal

You recognize the problem. You write clean code. You run it in your head. The interviewer writes something in their notepad. You will never, ever know what it says.

In each of these five problems, there is a correct "obvious" solution and a better one that is faster, uses less memory, or both. The gap isn't obscure knowledge. It's that your first instinct mislabels what the problem is actually asking. The constraints aren't decoration. They're instructions. Read them differently and the faster, leaner solution falls out.

Every one of these problems has a moment where the interviewer is waiting for exactly this.

Median of Two Sorted Arrays: Merging Is the Wrong Move

The obvious play: merge both arrays, read the middle index. O(m + n) time, O(m + n) space. Correct. The problem statement helpfully hints at O(log(m + n)) and then just... waits.

The merge approach gets the answer but asks the wrong question. The real question isn't "which elements are in the merged array?" It's "where is the cut that splits everything into two equal halves?" A median is defined by a partition, not a sorted list. If you find a split point i in nums1 and a corresponding split j = half - i in nums2 such that everything left of both cuts is smaller than everything right, you have your median. No merged array, no extra space.

You only need four boundary values to check the partition: nums1[i-1], nums1[i], nums2[j-1], nums2[j]. Binary search on i from 0 to m, adjusting based on whether the current split is too far left or right. Run the binary search on the smaller array for O(log(min(m, n))).

def find_median(nums1: list[int], nums2: list[int]) -> float:
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    half = (m + n + 1) // 2
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = half - i
        if i < m and nums2[j - 1] > nums1[i]:
            lo = i + 1
        elif i > 0 and nums1[i - 1] > nums2[j]:
            hi = i - 1
        else:
            left_max = (nums2[j - 1] if i == 0
                        else nums1[i - 1] if j == 0
                        else max(nums1[i - 1], nums2[j - 1]))
            if (m + n) % 2 == 1:
                return float(left_max)
            right_min = (nums2[j] if i == m
                         else nums1[i] if j == n
                         else min(nums1[i], nums2[j]))
            return (left_max + right_min) / 2.0

Once you reframe "find the median" as "binary search on a cut," the algorithm follows. The hard part is making that initial shift.

Find the Duplicate: Your Array Is Secretly a Graph

Hash set: O(n) time, O(n) space. Sorting: O(n log n) time, O(1) space. Both correct. Neither optimal. And the optimal approach looks nothing like either.

The constraint that every value is in [1, n] sounds like a footnote. It isn't. Because values are in [1, n], every element is a valid index, which means every index i has a directed edge to nums[i]. With n + 1 elements and values capped at n, the pigeonhole principle guarantees a duplicate. Two indices point to the same node. That's a cycle. The duplicate is where the cycle begins.

From there, Floyd's cycle detection: run slow at one step and fast at two steps until they meet inside the cycle, then reset slow to index 0 and walk both one step until they meet again. Meeting point is the entrance, which is the duplicate.

def find_duplicate(nums: list[int]) -> int:
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

"Find a duplicate in an array" reads like a frequency problem. It was a graph problem the entire time. The array was lying. Remove the [1, n] constraint and Floyd's breaks entirely. The constraint isn't a footnote, it's the load-bearing piece. For the two-phase proof in detail, see Floyd's cycle detection explained.

Trapping Rain Water: You Don't Actually Need Both Sides

Standard DP: compute left_max[i] and right_max[i] in two passes, store both arrays, third pass computes min(left_max[i], right_max[i]) - height[i]. Correct. O(n) time, O(n) space.

The O(1) space version requires believing something that feels wrong. If left_max < right_max, the water at the left pointer is fully determined by left_max, and you don't need to know the exact right maximum. The right pointer sits on a bar of height right_max. The true maximum anywhere between the pointers is at least right_max. So min(left_max, true_right_max) = left_max. Compute the water, advance left. No need to look right.

def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

The DP approach feels necessary because rain water depends on both sides. The two-pointer version works because you don't need both sides exactly. The smaller side is always the bottleneck, and the pointers maintain that guarantee from the outside in.

Majority Element: Counting Everything Is Overkill

Hash map: O(n) time, O(n) space. Sorting: O(n log n), O(1) space. Neither is optimal.

Boyer-Moore finds the majority element in O(n) time and O(1) space through a cancellation argument. Pair every non-majority element with a distinct majority element and remove both. The majority appears more than n/2 times, so it outlasts every pairing. The algorithm simulates this without actually pairing: track a candidate and a count, increment when you see the candidate, decrement otherwise, replace candidate when count hits zero.

def majority_element(nums: list[int]) -> int:
    candidate, count = None, 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate

One caveat that actually matters: Boyer-Moore returns a candidate even when no majority element exists. The algorithm does not know it's wrong. It just hands you something and walks away.

Boyer-Moore without the second-pass verification, basically.

For LeetCode where a majority is guaranteed, the single pass is safe. For anything else, add a second pass to verify. The Boyer-Moore voting algorithm deep dive covers the n/3 generalization if you need it.

Maximum Subarray: The Textbook Taught You the Slow Answer

CLRS Section 4.1 uses maximum subarray as the motivating example for divide-and-conquer. Split at midpoint, find the best subarray in each half and crossing the middle, combine. O(n log n). Then, in Exercise 4.1-5, CLRS asks for the O(n) solution. As homework.

If you reach for divide-and-conquer in an interview because that's where you met this problem, you did exactly what the textbook intended. Not what the interviewer wanted.

Kadane's algorithm is O(n). The maximum subarray ending at index i is either nums[i] alone or nums[i] appended to the best subarray ending at i - 1. If the previous best is negative, start fresh. One variable, one pass.

def max_subarray(nums: list[int]) -> int:
    best = current = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)
        best = max(best, current)
    return best

Initialize to nums[0], not 0. Initializing to zero fails on all-negative arrays where the correct answer is the least-negative element. Jay Kadane designed this in under a minute at a 1984 CMU seminar after hearing the problem described. The divide-and-conquer version took longer to derive and is still what most textbooks teach first.

The Pattern Behind Every Optimal Solution

Each problem exploits a different cognitive trap:

• Median: "I need the sorted data" when you only need the boundary
• Find Duplicate: "This is a frequency problem" when it's a graph problem
• Trapping Rain Water: "I need both sides" when the smaller side is sufficient
• Majority Element: "I need to track all counts" when net cancellation is enough
• Maximum Subarray: "Divide and conquer is the right paradigm" when one scan is enough

The question worth asking before every problem is whether your approach uses all of the constraints. The range [1, n] in the duplicate problem isn't a random detail, it's the load-bearing constraint that makes Floyd's work. The guarantee that a majority exists isn't flavor text, it's what makes the single pass safe.

When you find yourself building data structures to store what you've already seen, ask whether the constraints let you derive that information without storing it. That question is where O(1) space solutions come from.

If you want to pressure-test whether you actually produce these solutions under time pressure, SpaceComplexity runs voice-based mock interviews on problems exactly like these. Knowing the trick while calmly reading an article is a different thing from finding it with someone watching the clock.

Quick Recap

• Median of Two Sorted Arrays: Binary search on partition count, not elements. O(log min(m,n)) time, O(1) space.
• Find the Duplicate Number: Every value is a valid index. The duplicate is the cycle entrance. Floyd's gives O(n) time, O(1) space.
• Trapping Rain Water: Two pointers. The smaller side determines water. No precomputed arrays needed.
• Majority Element: Boyer-Moore voting. Net surplus, one pass, O(1) space. Requires majority to be guaranteed.
• Maximum Subarray: Kadane's algorithm. Extend or restart. O(n) beats O(n log n).

Further Reading

• Median of Two Sorted Arrays, GeeksforGeeks
• Cycle Detection, Wikipedia
• Boyer-Moore Majority Vote Algorithm, Wikipedia
• Maximum Subarray Problem, Wikipedia
• Trapping Rain Water, LeetCode