Arrays & Hashing

LeetCode 1

LeetCode #1Difficulty: EasyNeetCode 150

LeetCode 1: Two Sum

LeetCode

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

Problem Description

Given an array of integers `nums` and an integer `target`, return indices of the two numbers such that they add up to `target`. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

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

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

Explanation: Because nums[1] + nums[2] == 6, we return [1, 2].

Constraints:
  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • Only one valid answer exists.

Core Mental Model

When searching for a pair (a, b) such that a + b = target, knowing `a` immediately locks in the exact value of `b` as `target - a`. Instead of scanning the rest of the array with an inner loop (O(N²)), we store visited elements in a Hash Table. In each iteration, we ask: 'Has my required complement already been seen?' If yes: we return the stored index and current index in O(1). If no: we insert the current value into the table and proceed.

Formal Loop Invariant

Invariant: At step i, the Hash Table contains exactly the elements nums[0 ... i-1]. If a pair exists with nums[i], its complement has already been recorded in the map.

Key Architectural Takeaway:

Hash tables convert time bottlenecks into linear space by indexing previous elements for O(1) queries.

Asymptotic Complexity Analysis

Time ComplexityO(N) Single pass over N elements with O(1) average hash lookups and inserts.
Space ComplexityO(N) Stores at most N elements in the hash map before finding match.

Bottleneck: Brute force scans all N*(N-1)/2 pairs in O(N²). Hash table trades O(N) RAM to reduce lookup from O(N) to O(1).

Edge Cases & Screener Traps

  • Duplicate numbers that sum to target (e.g. [3, 3], target = 6)
  • Negative numbers with negative target (e.g. [-3, 4, 3, 90], target = 0)
  • Zero as an element (nums = [0, 4, 3, 0], target = 0)