🧠 Crack Google Interview: The sum of two

Google LeetCode

Ever wondered what a real Google interview question looks like? Here’s one of the most famous algorithm challenges — deceptively simple, but packed with insight. It tests how well you think under pressure, and how efficiently you can use data structures. Think you can crack it?

“Given an array of integers, return the indices of the two numbers such that they add up to a specific target.”
✅ Each input has exactly one solution
🚫 You may not use the same element twice

Example

Input: nums = [2, 7, 11, 15], target = 9 
Output: [0, 1] // because 2 + 7 = 9

This problem may seem straightforward at first glance, but solving it efficiently — in linear time — requires more than just looping through numbers. The real challenge lies in recognizing how to leverage the right data structure to reduce time complexity. Let’s walk through an elegant solution using a hash map that gets the job done in a single pass.

Robust Rust

Here's a clean and efficient solution in Rust using a hash map.

use std::collections::HashMap;

struct Solution;

impl Solution {
    pub fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
        let mut index_map = HashMap::new();

        for (i, &num) in nums.iter().enumerate() {
            let complement = target - num;
            if let Some(&j) = index_map.get(&complement) {
                return Some((j, i));
            }
            index_map.insert(num, i);
        }

        None
    }
}

How it works?

Let’s unpack this in plain English!

• We loop through the list once (O(n) time).

• For each number, we compute the "complement" - the number that would sum with it to reach the target.

• We check if we've already seen that complement in the hash map:

  • ✅ Yes → return the index of that complement + the current index.

  • ❌ No → store the current number and its index for later.

This avoids nested loops entirely - goodbye O(n²)!

Example walkthrough

Let’s walk through nums = [2, 7, 11, 15], target = 9.

1. i = 0, num = 2 → complement = 7 → not found
   ➜ Save 2 with index 0

2. i = 1, num = 7 → complement = 2 → found in map at index 0
   ➜ Return (0, 1)

That’s it. One pass. Done.

Classy C++

Here’s how to solve it in C++ using unordered_map for constant-time lookups.

#include <vector>
#include <unordered_map>
#include <optional>
#include <utility>

class Solution {
public:
    static std::optional<std::pair<int, int>> twoSum(const std::vector<int>& nums, int target) {
        std::unordered_map<int, int> index_map;

        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            if (index_map.find(complement) != index_map.end()) {
                return std::make_pair(index_map[complement], i);
            }
            index_map[nums[i]] = i;
        }

        return std::nullopt; // should not happen if one solution exists
    }
};

What’s happening under the hood?

Here’s the intuition behind the code:

• We use an unordered_map<int, int> to store numbers we've already seen and their indices.

• As we iterate:

  • We compute the complement of the current number (i.e. target - nums[i]).

  • If we’ve already seen the complement, we return the pair of indices.

  • Otherwise, we store the current number and its index in the map.

This approach ensures each element is visited only once — making it very efficient.

Example walkthrough

Let’s walk through nums = [2, 7, 11, 15], target = 9.

1. i = 0 → nums[i] = 2
   complement = 9 - 2 = 7 → not in map
   ➜ Save 2 with index 0

2. i = 1 → nums[i] = 7
   complement = 9 - 7 = 2 → found in map at index 0
   ➜ Return (0, 1)

Perfect match found in a single pass.

Fancy Python

from typing import List, Optional, Tuple

class Solution:
    @staticmethod
    def two_sum(nums: List[int], target: int) -> Optional[Tuple[int, int]]:
        index_map = {}
        
        for i, num in enumerate(nums):
            complement = target - num
            if complement in index_map:
                return (index_map[complement], i)
            index_map[num] = i
        
        return None  # If no solution found (shouldn’t happen per constraints)

What’s going on?

• You loop through the array once (O(n) time).

• For each number, you check whether the complement (i.e., target - num) already exists in your dictionary.

• If it does, you've found the pair and return their indices.

• If it doesn’t, store the current number and its index for future checks.

Why use a dictionary?

Dictionaries in Python offer average-case O(1) lookup time, making them perfect for this type of problem where you're checking for matches on-the-fly.

Example walkthrough

For nums = [2, 7, 11, 15] and target = 9:

1. i = 0 → num = 2
   complement = 9 - 2 = 7 → not in dictionary
   ➜ Store {2: 0}

2. i = 1 → num = 7
   complement = 9 - 7 = 2 → found! at index 0
   ➜ Return (0, 1)

Fast. Simple. Elegant.

⏱️ Time & space complexity

• Time Complexity O(n)

• Space Complexity O(n)

Why it’s interview gold

• Simple and elegant.

• Efficient in both time and space.

• Demonstrates mastery of hash maps, iteration, and early returns.

🧪 Your Turn

Got your own twist on the solution? Think you can make it even cleaner or faster? Share your approach in the comments - or reply to this post if you're reading via email. I’ll feature the most insightful submissions in the next issue. If you’re not already subscribed, now’s the time - I break down real interview problems like this every week, with code, intuition, and practical takeaways.