Five Coding Interview Time Complexity Floors. How Many Can You Guess?

The naive solution tells you the ceiling. The floor is what separates "I solved it" from "I understood it." Most interviews die in the gap between those two things.

For each problem below, commit to a time complexity estimate before reading the reveal. Write it down. No, actually write it down. I'll wait.

Problem 1: Median of Two Sorted Arrays

You have two sorted arrays, sizes m and n. Find the median of all m+n elements combined.

Write down your time complexity guess.

Optimal: O(log(min(m, n))) time, O(1) space.

Merge both arrays and it's O(m+n). That's the ceiling. The floor is much lower. Both arrays are already sorted, which means you can binary search for the right partition: how many elements from each array fall to the left of the median. Search on the smaller array, check if the partition is valid, adjust in log(min(m,n)) steps.

Most candidates who pass this problem do so in O(m+n). They walk out feeling good. Then the follow-up arrives: "Can we do better?" And the room goes quiet. That gap between ceiling and floor is exactly what the follow-up is designed to expose.

Problem 2: K-th Largest Element in an Unsorted Array

Find the k-th largest element. The array is not sorted.

Your guess?

Optimal: O(n) expected time, O(1) space.

Sort and index: O(n log n). That feels obvious. It's also what most people do, and it's fine, and the interviewer is already writing "can we do better?" in their notes.

What they're waiting for you to notice: you only need one rank. Not a complete ordering. Not a sorted phonebook. QuickSelect partitions around a pivot and recurses into one half, throwing the other away entirely. Expected O(n). The comparison-based lower bound for sorting is Ω(n log n), but selection has no such constraint. You're not building a total order, so you shouldn't pay for one.

When the interviewer says "nice, but can we do better?" and you sort-of see where this is going Your algorithm is correct. The exam just started.

Problem 3: Find the Duplicate (Read-Only, O(1) Space)

An array of n+1 integers where every value is in [1, n]. Exactly one value appears at least twice. You cannot modify the array. Use O(1) extra space.

This one is harder. Take your time.

Optimal: O(n) time, O(1) space.

Hash set: O(n) time, O(n) space. Gets you the right answer, fails the constraints. Sort (if you could modify the array): O(n log n) time. Also fails the constraints. Neither satisfies both at once.

The non-obvious approach looks like a magic trick the first time you see it. Treat the array as a linked list where the value at index i is a pointer to index arr[i]. Every value is in [1, n] and there are n+1 elements, so the structure must contain a cycle. The duplicate value is the cycle's entry point, and Floyd's cycle detection finds it with two pointers and zero extra memory. LeetCode 287. If you haven't seen this reduction, read Floyd's Cycle Detection Algorithm for the full proof. Fair warning: the first time you see it, you will not believe it works.

Problem 4: Rotate an n×n Matrix In-Place

Rotate a square matrix 90 degrees clockwise. Do it in place.

You must touch every element, so time is Ω(n²). But what's the space complexity?

Optimal: O(n²) time, O(1) extra space.

The instinct is to allocate a copy, write into it, then overwrite the original. That costs O(n²) extra space. It also feels satisfying when it works, right up until you mention the space complexity and watch the interviewer's expression.

You don't need the copy. Transpose the matrix first (swap arr[i][j] with arr[j][i]), then reverse each row. Two in-place passes, no allocations. The two-step transform is equivalent to a 90-degree clockwise rotation. Most people who solve this correctly still allocate O(n²) space. They solved the problem and missed the floor.

Problem 5: Count Inversions in an Array

An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. Count the total number of inversions.

Your guess for optimal time?

Optimal: O(n log n) time.

Checking every pair is O(n²). That's the obvious approach, and it works, and an interviewer who's been through forty of these interviews in a week has seen it forty times.

The trick is counting inversions during a merge sort, for free. When merging two sorted halves and you pick an element from the right half before exhausting the left half, every remaining element in the left half forms an inversion with it. Count them as you merge. The inversion count piggybacks on a sort you were already doing. No extra work, no extra passes. Total: O(n log n).

The moment you realize you were doing n log n of work and could have been counting inversions the whole time Learning that merge sort was doing this for free the entire time.

The Intuition You're Actually Training

If you knew Problem 2's floor was O(n), you'd look for a selection algorithm before reaching for sort. If you knew Problem 4's space floor was O(1), you'd look for an in-place transform instead of allocating a copy. Knowing the floor narrows your search before you write a single line.

This is the half of algorithm intuition that grinding LeetCode doesn't build. You practice solving. You don't practice bounding. Those are different skills, and interviews test both. The follow-up question ("can we do better?") lands differently when you already have an answer.

Practice stating your complexity target out loud before you code. SpaceComplexity runs voice-based mock interviews where you have to justify every bound you claim, not just arrive at one after the fact.

If your solutions are correct but your complexity analysis comes late or vague, read Five Coding Interview Problems Where Your First Solution Isn't Optimal for more cases where the ceiling and floor diverge.