The DSA Patterns I’d Revise Before an Interview

Whenever I think about looking for a new, higher-paying Developer job, DSA interview problems are the first gatekeeper between me and the job. I have prepared for these problems in the past, but only until I get a new job. After getting the job, I feel no need to continue solving DSA problems. And after some time, if I wish to look for a job again and start preparing for DSA, it feels like starting again from the beginning. Even though the catch-up is fast, the hunt for DSA resources still feels like starting from scratch. I wish there were a resource that summarised all the patterns I had learnt during preparation, so I could quickly revisit every pattern before my next interview. This article is my endeavour towards fulfilling that wish.

Pattern 1: O(1) Lookup

Problem Statement

Suppose you are given an array of integers ([3, 1, 9, 2, 6]) and a target number (8). The problem is to find a pair of numbers in the array whose some is equal to the target number.

Brute Force Solution 1

Brute force solution is to iterate over all the possible pair, calculate sum of each pair, and check if its equal to the target.

def find_target_pair(array, target)
    for i in range(len(array) - 1):
        for j in range(i, len(array)):
            pair_sum = array[i] + array[j]
            if pair_sum == target:
                return (array[i], array[j])

The time complexity of this brute force solution is $O(N^2)$. The reason being in total there are $N(N+1)/2$ total pairs (where $N$ is the size of the array).

Brute Force Solution 2

Another way to think about the brute for solution is for each i-th number we look into the array and ask ourselves: does target - array[i] also exists in the array?

def find_target_pair(array, target)
    for i in range(len(array) - 1):
        remaining = target - array[i]
        for j in range(i, len(array)):
            if array[j] == remaining:
                return (array[i], array[j])

The time complexity is still $O(N^2)$, there is just a shift in perspective in the second brute force solution.

O(N) Solution

Inside the nested loop in the second brute force solution, we are only checking if remaining number exists, and there is a classic $O(1)$ solution to this. And that is hashmap. In python, set uses hashes to store elements and dictionary uses hash to store keys. We first store the input array numbers in a set and use the set to checking whether remaining exists or not.

def find_target_pair(array, target)
    numbers_set = set(array)
    for i in range(len(array) - 1):
        remaining = target - array[i]
        if remaining in numbers_set:
            return (array[i], remaining)

The time complexity is $O(N)$ and the space complexity is $O(N)$ as we are using extra space to store intermediary data (i.e. numbers_set) for faster lookup.

Lesson

Once you've arrived at a brute force solution, observe if you are searching for elements in data structures multiple times. Can I leverage hashmaps to make the algorithm faster.
If you are doing some kind of search in your data structure but the lookup is not straight forward, think about alternate ways to write the same brute-force solution, so that the lookup become straightforward.

Pattern 2: Two Pointers

Problem Statement

Suppose you are given a sorted array of integers ([1, 2, 3, 6, 9]) and a target number (8). The problem is to find a pair of numbers in the sorted array whose some is equal to the target number.

The problem statement is almost the same as the previous problem, with just one little difference, this time the array is sorted. Both the previous solutions i.e. $O(N^2)$ brute force and the optimized $O(N)$ still works. The optimized $O(N)$ solution had space complexity of $O(N)$ because it used an intermediate hashmap of size N in worst case scenario.

Solution

We can use two pointers (left and right) to exploit the sorted nature of the array to come up with $O(N)$ solution at $O(1)$ space complexity.

Step 1

Initially, left pointer points at the first element (1), and right pointer points at the last element (9) of the array. There sum 1 + 9 = 10 is greater than target (8).

Step 2

Ask yourself: can the last element (9) ever become part of the answer pair given the minimum number (the first element) is 1? The answer is no. Therefore, we can reduce our search space by excluding this element. Now, the right pointer points at the second last element (6) and the left pointer is still pointing at the first element (1).

The sum is 1 + 6 = 7 which is lesser than the target 8.

Step 3

Can 6 ever be a part of the solution, given the minimum number is 1? The answer this time is YES, as the array is sorted and we might have greater number after 1 which might help use achieve the target sum of 8. So we can't discard 6 from the search space.

But can 1 ever be a part of the solution given the maximum possible number in the search space is 6? The answer is NO. So, we can safely discard it from the search space. Now, the left pointer points at the second element which is 2. The sum of elements at left (2) and right (6) pointers is 2 + 6 = 8, which is our target sum. Therefore, the answer is (2, 6).

If we would've not found the pair at step 3, we would've continued further and at each step asked ourselves: can elements at the left or the right pointers could ever be the part of solution, and excluded them accordingly.

def two_sum_sorted(array, target):
    left = 0
    right = len(array) - 1
    while left < right:
        current_sum = array[left] + array[right]
        if current_sum == target:
            return (array[left], array[right])
        elif current_sum < target:
            # Need a larger sum → move left pointer right
            left += 1
        else:
            # Need a smaller sum → move right pointer left
            right -= 1
    return None

Lesson

Don't memorize pointer movements. Instead ask: what can I safely eliminate?

Abdullah Saquib