DSA Interview Follow-Up Questions: Optimise Brute Force Step by Step

You produce a correct nested-loop solution, but freeze when the interviewer asks, “Can you optimise it?” Use a repeatable sequence: confirm the contract, quantify the brute-force cost, identify repeated work, state an invariant, choose a data structure, then prove correctness and complexity. Apply it to one problem: given A = [4, -1, 7, 2, 11, 4] and target = 8, return two distinct original indices whose values add to the target.

1. DSA brute force is the specification, not a failed attempt

First fix the contract. The indices must be distinct and must refer to the original array. Negative and duplicate values are allowed, and any one valid pair is enough. Here, (0, 5) is valid because A[0] + A[5] = 4 + 4 = 8. The input [4] with target 8 has no answer because one element cannot be reused.

The baseline is direct:

for i = 0 to n - 2
    for j = i + 1 to n - 1
        if A[i] + A[j] == target, return (i, j)

For i = 0, it checks 4 + (-1) = 3, 4 + 7 = 11, 4 + 2 = 6, 4 + 11 = 15, and finally 4 + 4 = 8. It returns (0, 5) after five checks. This is the correctness baseline for every optimisation, a habit that also matters in technical interview preparation across core CS subjects.

2. DSA constraints expose the real bottleneck

In the no-solution or last-pair case, brute force examines

(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2

pairs. At n = 200,000, the count is 200,000 x 199,999 / 2 = 39,999,800,000 / 2 = 19,999,900,000 candidate pairs. That is scale arithmetic, not a runtime prediction.

For every value x, the inner loop repeatedly asks whether target - x occurs elsewhere. So “do better” becomes precise: can membership of the needed complement be answered without rescanning the array? Small constraints may permit the baseline. When pair enumeration dominates, optimise the complement search, not the addition.

3. The hash-map invariant turns the lookup into one pass

State the invariant first: just before index i is processed, seen maps values from indices 0 through i - 1 to an earlier index. Compute need = target - A[i], query seen, and only then insert A[i]. Query-before-insert guarantees distinct indices, including when need == A[i].

The pseudocode must preserve that order:

function twoSum(A, target):
    seen = empty map
    for i = 0 to length(A) - 1:
        x = A[i]
        need = target - x
        if seen contains need:
            return (seen[need], i)
        seen[x] = i
    return NO_PAIR

4. Correctness and complexity need short proofs

Soundness: if the algorithm returns (j, i), then j < i because j came from seen. Since A[j] = target - A[i], the distinct indices hold values that sum to the target.

Completeness: take any valid pair (p, q) with p < q. When index q is processed, seen contains a value equal to A[p]. Since A[p] = target - A[q], the lookup finds a valid earlier partner.

In the worst case, brute force takes Theta(n^2) time and O(1) auxiliary space. At most one lookup and insertion per element give expected Theta(n) time and O(n) auxiliary space. “Expected” reflects the constant-time hash-operation assumption.

An interview-ready summary is: “I removed the repeated linear complement scan by storing earlier values; under expected constant-time hash operations, time falls from quadratic to linear at the cost of linear extra space.”

5. The O(1)-extra-space follow-up changes the choice

Before sorting, ask what may change. If values are enough, reordering is allowed, and one pair is required, sort to [-1, 2, 4, 4, 7, 11] and use two pointers. For target 8:

• -1 + 11 = 10, above the target, so move the right pointer in.

• -1 + 7 = 6, below the target, so move the left pointer in.

• 2 + 7 = 9, above the target, so move the right pointer in.

• 2 + 4 = 6, below the target, so move the left pointer in.

• 4 + 4 = 8, so the pair is found.

Sorting costs O(n log n) time. An in-place sort such as heapsort holds auxiliary space at O(1), and the two-pointer scan adds nothing beyond that, so sorting in place is the genuine constant-extra-space answer whenever only values matter and the original order may be lost. To preserve indices instead, sort copied (value, originalIndex) pairs: [(-1,1), (2,3), (4,0), (4,5), (7,2), (11,4)]. Two pointers then return (0,5), but the copy costs O(n) extra space, which is the very cost the follow-up asked you to remove. Explaining that choice out loud is its own skill, and Resume & Interview Preparation is where that practice sits.

6. DSA follow-up questions test whether the contract still holds

For each follow-up, restate the new constraint, identify which earlier assumption breaks, adapt the invariant, and recompute time and space. Do not say “hashing is always best”. During timed Coding Round Strategy for Placements practice, explain the baseline before coding the optimised version.

7. Brute-force optimisation traps need counterexamples

Inserting before querying accepts the invalid input [4], target 8, by pairing index 0 with itself. Sorting raw values loses original indices. Storing only one index per value cannot return every pair when that is the contract. Calling hashing simply O(n) hides the expected constant-time assumption. Jumping directly to hashing also removes the baseline used to check correctness.

Test the contract with cases that expose those failures:

Alternative indices are acceptable only when an input has multiple solutions. Confirm that the optimised method handles every counterexample without changing the mutation, output, or original-index requirements.

8. The short version: optimise by removing repeated work

The reusable ladder is compact: confirm the contract, write and cost the brute force, locate the repeated query, state what must remain true, choose the operation and data structure, trace a duplicate-sensitive example, prove correctness, then state the time-space trade-off. Here that reasoning preserves the allowed answer (0,5) while removing repeated complement scans.

If you want structured practice in delivering this reasoning, the Interview & Resume Preparation Course is an optional next step. For more implementation practice, use Coding for Placements.