Two Sum

Google Interview Question

Problem Overview

Difficulty: Easy
LeetCode Pattern: Arrays & Hashing

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Input: 
· nums = [3,3]
· target = 6
Output: 
· [0,1]

Input: 
· nums = [2,7,11,15]
· target = 18
Output: 
· [1,2]

---

Step 1: Clarify Requirements

• Can the input array be empty?

  • Yes.

  • Return empty array.

• Will it be sorted?

  • No.

---

Step 2: Discuss Approaches

1/ Nested Loop (Brute Force ⚠️)

• Logic:

  • Start with value at index 0

  • Check its sum with all other values

  • If it adds up to target:

    • return the indices

  • Otherwise:

    • increment index and repeat

• Big O:

  • Time Complexity: O(n²)

  • Space Complexity: O(1)

---

2/ Use a Map (Optimal ✅)

• Logic:

  • Initialize an empty map

  • Iterate through the list

  • For each element:

    • Check if complement is in map

    • If it exists:

      • We found a solution

    • Otherwise:

      • Store in map and continue

  • Return empty array if no pair found

• Big O:

  • Time Complexity: O(n)

  • Space Complexity: O(n)

---

Step 3: Write Code (Optimal)

Python

---

Java

---

C++

---

Step 4: Answer Follow-Ups

• What if the array is sorted?

  • Use two-pointer technique

  • No map is needed

• How to return all valid pairs?

  • Store pairs in a list instead of returning immediately

  • Return the list after processing all elements