Welcome to Day 1 of the Tekraze DSA series. Every day we pick one problem, understand it like a human first, and then solve it in Java, Python and Rust. Java and Python because most interviews still use them, and Rust because it keeps showing up in crypto, blockchain and systems jobs.
What will this daily DSA series cover?
We start easy and climb step by step. Here is the rough roadmap so you know where we are going.
- Arrays and strings
- Hashing
- Two pointers
- Sliding window
- Stacks and queues
- Linked lists
- Binary search
- Recursion and backtracking
- Trees
- Heaps
- Graphs
- Dynamic programming
Today we kick things off with the most famous warm up of all time, the Two Sum problem. It looks tiny, but it teaches the single most useful trick in coding interviews: trading a little memory for a lot of speed.
What is the Two Sum problem?
You get an array of integers nums and an integer target. Return the indices of the two numbers that add up to target. You can assume exactly one answer exists, and you can’t use the same element twice.
Here is a quick example of the Two Sum problem.
text
Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Why: nums[0] + nums[1] = 2 + 7 = 9
How should you think about the Two Sum problem in plain words?
Imagine you walk through the array holding a notebook. At each number you ask one question: have I already seen the number that would complete this pair? If target is 9 and you are standing on 7, you need a 2. If 2 is in your notebook, you are done. If not, write 7 down and keep walking.
That notebook is a hash map. It stores each value with its index, and checking it takes roughly constant time.
What does the brute force Two Sum problem solution look like?
The honest first idea is to try every pair. Pick one number, then check it against every number after it.
python
def two_sum_brute(nums, target):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
This runs in O(n²) time because of the nested loops, and O(1) space. It works, and it is fine to say it out loud in an interview. But with 10,000 numbers you are doing around 50 million checks, so we can do much better.
How do we get the optimal O(n) solution to the Two Sum problem?
Use the notebook idea. For each number, compute need = target - num. If need is already in the map, return both indices. Otherwise, store the current number and its index. One pass, done.
Time is O(n) since every lookup and insert is O(1) on average. Space is O(n) for the map in the worst case.
Also Read: Time and Space Complexity Explained
Java solution for the Two Sum problem
java
import java.util.*;
public class Solution {
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) {
return new int[]{seen.get(need), i};
}
seen.put(nums[i], i);
}
return new int[]{};
}
public static void main(String[] args) {
System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9))); // [0, 1]
System.out.println(Arrays.toString(twoSum(new int[]{3, 2, 4}, 6))); // [1, 2]
System.out.println(Arrays.toString(twoSum(new int[]{3, 3}, 6))); // [0, 1]
System.out.println(Arrays.toString(twoSum(new int[]{-1, -2, -3, -4, -5}, -8))); // [2, 4]
}
}
Python solution for the Two Sum problem
python
def two_sum(nums, target):
seen = {} # value -> index
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
print(two_sum([3, 2, 4], 6)) # [1, 2]
print(two_sum([3, 3], 6)) # [0, 1]
print(two_sum([-1, -2, -3, -4, -5], -8)) # [2, 4]
Rust solution for the Two Sum problem
rust
use std::collections::HashMap;
fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
let mut seen: HashMap<i32, usize> = HashMap::new();
for (i, &num) in nums.iter().enumerate() {
let need = target - num;
if let Some(&j) = seen.get(&need) {
return Some((j, i));
}
seen.insert(num, i);
}
None
}
fn main() {
println!("{:?}", two_sum(&[2, 7, 11, 15], 9)); // Some((0, 1))
println!("{:?}", two_sum(&[3, 2, 4], 6)); // Some((1, 2))
println!("{:?}", two_sum(&[3, 3], 6)); // Some((0, 1))
println!("{:?}", two_sum(&[-1, -2, -3, -4, -5], -8)); // Some((2, 4))
}
In Rust we return Option<(usize, usize)> instead of an empty array. That makes the “no answer” case explicit, and the compiler forces the caller to handle it.
All three programs were run against the same four tests, including duplicates like [3, 3] and negative numbers, and every one printed the expected answer.
What are the best tips for solving the Two Sum problem?
- Spot the pattern. Whenever a problem says “find two items that combine into X”, think of a hash map that stores what you have seen. Pairs plus fast lookup almost always means hashing.
- Look for the complement, not the pair. Rewrite
a + b = targetasb = target - a. Now you search for one value instead of two. - Check before you insert. Look up
needfirst and only then store the current number. This one habit handles [3, 3] correctly and stops you from pairing an element with itself. - Store value to index. The question asks for indices, so the key is the number and the value is where you saw it.
- Sorted input? Use two pointers. If the array is already sorted, put one pointer at each end and move inward. That gives O(1) extra space. We will do this properly on the two pointers day.
- Test the edge cases. Duplicates, negatives, zero, and the answer being the last two elements are the ones that catch people.
- Interview tip. Say the brute force first, give its complexity, then explain the trade of space for time. Interviewers care about that reasoning as much as the final code.
What are the common mistakes with the Two Sum problem?
- Inserting into the map before checking, so [3] with target 6 pairs with itself.
- Sorting the array to use two pointers and then returning the new indices instead of the original ones.
- Returning the values instead of the indices.
- Ignoring integer overflow in languages like Java or Rust when numbers are huge. Use
longori64if the constraints demand it. - Forgetting what to return when no pair exists.
Where is the Two Sum problem pattern used in the real world?
The “have I seen the complement” idea shows up in many places. Accounting tools can use it to match a debit with a credit of the same amount. Fraud checks can look for pairs of transactions that add up to a suspicious total. Caching follows the same rule: remember what you saw so you never search twice.
What comes next in the series?
Tomorrow we stay with arrays and hashing and build on today’s trick. Try solving it once more without looking, in a language you are less comfortable with. If you want, share your Rust version in the comments.
Two Sum problem FAQs
Why is a hash map faster than two loops for the Two Sum problem?
A hash map lookup takes O(1) time on average, so checking for the complement is instant. Two loops compare every pair, which takes O(n²) time.
Can the Two Sum problem be solved without extra space?
Yes, if the array is sorted you can use two pointers from both ends for O(1) extra space. On unsorted input you would need to sort first, which costs O(n log n) time, and track the original indices.
What happens with duplicate numbers like [3, 3] and target 6?
Because we check the map before inserting, the second 3 finds the first one and returns [0, 1] correctly.
Which language is best for DSA interviews?
Use the one you write fastest without bugs. Python is short, Java is common in big companies, and Rust is a strong plus for crypto and systems roles.
Is the Two Sum problem still asked in interviews?
It is a common warm up question, and the same idea appears inside bigger problems like 3Sum and subarray sums.
