0DSA for Placements: Two Sum – From Brute Force to Optimised Solutions
1. Introduction
Solving a programming problem is not just about writing code. In technical interviews, recruiters want to understand how you approach a problem, analyse possible solutions and optimise your algorithm.
Let's explore one popular DSA interview problem: Two Sum.
2. Problem Statement
Given an integer array and a target value, find the indices of two distinct elements whose sum equals the target.
Example:
Array = [2, 7, 11, 15]
Target = 9
Expected Output = [0, 1]
Explanation: Array[0] + Array[1] = 2 + 7 = 9.
3. Approach 1: Brute Force
The simplest approach is to compare every possible pair of elements.
Python implementation:
def two_sum(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
print(two_sum([2, 7, 11, 15], 9))Output:
[0, 1]Complexity Analysis:
-
Time Complexity: O(n²)
-
Auxiliary Space Complexity: O(1)
The nested loops repeatedly examine pairs of elements. This solution works, but becomes inefficient for large arrays.
4. Approach 2: Optimised Solution Using HashMap
Can we avoid checking every possible pair?
Yes!
For each element x, calculate:
Complement = Target − x
Instead of searching the remaining array repeatedly, store previously visited elements in a HashMap.
Python implementation:
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
print(two_sum([2, 7, 11, 15], 9))Output:
[0, 1]5. Dry Run of the Optimised Algorithm
Array = [2, 7, 11, 15]
Target = 9
| Index | Current | Complement | Decision |
|---|---|---|---|
| 0 | 2 | 7 | Not found; store 2 → 0 |
| 1 | 7 | 2 | Found! Return [0, 1] |
The algorithm stops as soon as the required pair is identified.
6. Complexity Comparison
| Parameter | Brute Force | HashMap |
|---|---|---|
| Time | O(n²) | O(n) average |
| Auxiliary Space | O(1) | O(n) |
The optimised solution trades additional memory for faster searching.
Important interview point: Check for the complement before inserting the current element into the HashMap. This prevents using the same array element twice and correctly handles duplicates such as [3, 3], target = 6.
7. What Does an Interviewer Expect?
When solving a DSA problem, practise the following sequence:
-
Understand the problem and constraints.
-
Identify edge cases.
-
Explain the brute-force approach.
-
Analyse its time and space complexity.
-
Identify the opportunity for optimisation.
-
Write the optimised code.
-
Explain the complexity and test the solution.
Remember: A good candidate explains the reasoning, not just the final code.
Continue Your Placement Preparation
This problem is a small introduction to the problem-solving approach used in technical interviews.
The 50-Hour Placement Accelerator Programme is designed to develop structured DSA learning, algorithmic thinking, coding practice, complexity analysis and interview problem-solving skills for final-year BTech and MCA students.
Interested in preparing for technical placements?
Explore my UrbanPro teaching profile and enquire about the Placement Accelerator Programme.
Learn to think. Learn to optimise. Prepare to solve.
