[Leetcode] two sum

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.

Example 1:

1
2
3

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

1
2

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

Example 3:

1
2

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

Constraints:

• \(2 \leq \text{nums.length} \leq 10^4\)
• \(-10^9 \leq \text{nums[i]} \leq 10^9\)
• \(-10^9 \leq \text{target} \leq 10^9\)
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than \(O(n^2)\) time complexity?

Approach 1: Brute Force

Algorithm

The brute force approach is simple. Loop through each element \(x\) and find if there is another value that equals to target−\(x\)

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

from __future__ import annotations

class Solution:
    # brute-force two sums solutions
    def two_sum(self, nums: list[int], target: int) -> list[int]:
        '''
        Return indices i, j such that nums[i] + nums[j] == target.
        Args:
            nums: List of integers to search.
            target: The sum we want two elements of nums to add up to.

        Returns:
            A list with two indices [i, j]. Order does not matter.

        Note:
            LeetCode guarantees exactly one valid answer.
        '''
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[j] == target - nums[i]:
                    return [i,j]
        return []
    
def main() -> None:
    sol= Solution()
    print(sol.two_sum([2, 7, 11, 15], 9))
    print(sol.two_sum([3, 2, 4], 6)) 
    print(sol.two_sum([3, 3], 6))

if __name__ == "__main__":
    main()

Complexity Analysis

• Time complexity: \(O(n^2)\). For each element, we try to find its complement by looping through the rest of the array which takes \(O(n)\) time. Therefore, the time complexity is \(O(n^2)\).
• Space complexity: \(O(1)\). The space required does not depend on the size of the input array, so only constant space is used.

explanation

1
2
3
4
5
6

from typing import List

class Solution:
 def twoSum(self, nums: List[int], target: int) -> List[int]:
     ...

from typing import List imports the List type for type hints. (on Python 3.9+, we can write list[int] and skip this import.)

class Solution: calls code as Solution().twoSum(...). So the function to live inside a class named Solution.

def twoSum(self, nums: List[int], target: int) -> List[int]: defines a method named twoSum.

• self is the instance of Solution. We don’t use it here; it’s just the method signature.
• nums: List[int] is a type hint: “nums should be a list of integers”.
• target: int means “target should be an integer”.
• -> List[int] means “this function returns a list of integers” (the two indices).
• Type hints don’t change runtime behavior; they help readers and tools.

1
2

            return [i,j]
return []

• return [i, j] exits the function immediately when a pair is found.

• The trailing return [] only runs if the loops finish without finding any pair.

1
2

if __name__ == "__main__":
    main()

__ are called “dunder” (double-underscore) names, e.g. __init__, __str__, __name__. These are special identifiers reserved by Python for language features. We generally don’t invent new dunder names ourself—use only the ones Python defines.

__name__ vs "__main__" vs main

• __name__ — a built-in variable that Python sets for every module (file).
• "__main__" — a string literal. Python sets __name__ to this string only for the file that’s being executed directly (e.g., python app.py).
• main — just a normal function name we chose. It has nothing to do with "__main__" except by convention.

So this snippet means: “If this file is the entry script, then call the function main().” If the file is imported by another module, __name__ will be the module’s name (like "app"), the condition is False, and main() will not run.

Tiny demo (what happens when run vs import)

app.py

1
2
3
4
5
6
7

def main() -> None:
    print("Running as a script")

print(f"In app.py, __name__ is: {__name__}")

if __name__ == "__main__":
    main()

• Run python app.py → prints:

  1 2	In app.py, __name__ is: __main__ Running as a script

other.py

1
2

import app
print("Imported app; not running its main().")

• Run python other.py → prints:

  1 2	In app.py, __name__ is: app Imported app; not running its main().

Supplements

Type annotations && method

Here, we provide a detailed explanation of type annotations and methods.

[[leetcode-1-2-two-sum-type-annotation]]

instance

As for the instance, it doesn’t have to be named self, but we should name it self (and cls for class methods). That’s the Python convention (PEP 8), and most linters/IDEs expect it. e.g.

1
2
3
4
5
6
7
8
9
10
11
12
13

from __future__ import annotations
from dataclasses import dataclass

@dataclass
class User:
    name: str

    @classmethod
    def from_first_last(cls, first: str, last: str) -> User:
        """Alternate constructor that returns cls(...), not hard-coded User(...)."""
        return cls(name=f"{first} {last}")

u = User.from_first_last("Ada", "Lovelace")  # calls on the class; receives cls=User

1
2

@decorator
def f(): ...

1
2

def f(): ...
f = decorator(f)

1
2
3
4
5

@decorator
class C: ...
# is the same as:
class C: ...
C = decorator(C)

1
2
3
4
5
6
7
8
9
10

from dataclasses import dataclass

@dataclass
class Point:
    x: float
    y: float

p = Point(3.0, 4.0)
print(p)           # Point(x=3.0, y=4.0)
print(p.x, p.y)    # 3.0 4.0

1
2
3
4
5
6
7
8
9

from dataclasses import dataclass

@dataclass(order=True, frozen=True)
class Card:
    rank: int
    suit: str

# order=True -> cards can be compared/sorted by (rank, suit)
# frozen=True -> instances are immutable

1
2
3
4
5
6
7
8
9
10

class User:
    def __init__(self, name: str) -> None:
        self.name = name

    @classmethod
    def from_first_last(cls, first: str, last: str) -> "User":
        # cls is the actual class we called on (User or a subclass)
        return cls(f"{first} {last}")

u = User.from_first_last("Ada", "Lovelace")

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Counter:
    count: int = 0  # class variable (shared by all instances)

    def bump(self) -> None:
        type(self).count += 1  # or self.__class__.count += 1

    @classmethod
    def reset(cls) -> None:
        cls.count = 0

Counter.reset()
c1, c2 = Counter(), Counter()
c1.bump(); c2.bump()
print(Counter.count)  # 2

decorators

A decorator is just a callable that takes a function and returns a new one, often a wrapper, letting us extend behavior while keeping functions clean and following the Open–Closed Principle.

[[leetcode-1-1-two-sum-type-decorators]]

range

How range works?

range can be called in three standard forms:

• range(stop) → start defaults to 0, step defaults to 1.
• range(start, stop) → step defaults to 1.
• range(start, stop, step) → full control (step ≠ 0; can be negative).

return

Quick contrasts:

• continue: skip to the next iteration of the current (innermost) loop.
• break: exit the innermost loop only (outer loop keeps running).
• return: exit the function (all loops stop).

Once a return runs, the function exits immediately and any code after that return in the same function will not execute.

Approach 2: Two-pass Hash Table

Idea: First build a dictionary value -> index for all elements. Second pass: for each i, compute complement = target - nums[i]; if complement is in the dict at some j != i, return [i, j].

• Time: O(n) average (dict lookups are amortized O(1)).
• Space: O(n).
• Logic note: Storing the last index for each value still works; the j != i check prevents reusing the same element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

from __future__ import annotations

class Solution:
    """two pass hash table solution for two sum"""
    def two_sum(self, nums: list[int], target: int) -> list[int]:
        """
        Return indices [i, j] with nums[i] + nums[j] == target.

        This performs two passes:
          1) Build a mapping from value -> last index.
          2) For each index, look up its complement.

        Args:
            nums: Input list of integers.
            target: Desired sum of two distinct elements.

        Returns:
            Two indices [i, j] whose values sum to target. Order is not important.
        """
        # dict[int,int] is type annotation
        index_of: dict[int,int]={}
        
        # Pass 1: map each value to its (last) index.
        for i,x in enumerate(nums):
            index_of[x] = i

        # Pass 2: for each position, see if the complement exists at a different index.
        for i,x in enumerate(nums):
            nums_complement = target - x
            j = index_of.get(nums_complement)
            if j is not None and j!=i:
                return [i,j]
        return []

def main() -> None:
    sol = Solution()
    print(sol.two_sum([2, 7, 11, 15], 9))
    print(sol.two_sum([3, 2, 4], 6)) 
    print(sol.two_sum([3, 3], 6))


if __name__ == "__main__":
    main()

Syntax

is and is not are identity operators. They check whether two variables refer to the same object, not just equal values. This is why we write:

• x is None / x is not None ✅ (recommended by PEP 8)
• rather than x == None ❌ (works but not idiomatic)

Why this matters for j in Two Sum:

• 0 is a valid index but is falsy (if j: would skip it).

• None means “missing.”

• So we must test specifically for None:

  1 2	if j is not None and j != i: ...

Other “English-like” operators Python uses

• and, or, not
• in, not in
• is, is not

They’re real operators, not sugar—Python is deliberately designed to read close to English for clarity.

Rule of thumb:

• Use is / is not only for identity checks, especially None (and singletons).
• Use == / != for value comparisons.

Supplements

enumerate

enumerate is a built-in that lets us loop over both the index and the value of any iterable (list, tuple, string, file, generator) without writing range(len(...)).

What it does

1
2

for index, value in enumerate(iterable, start=0):
    ...

• iterable: anything we can loop over (list[int], str, file, etc.).
• start: the first index to use (default 0; set start=1 if we want 1-based numbering).
• It yields pairs: (index, value) lazily (no copying of the data).

vs range(len(seq))

• Clearer: for enumerate we see both index and value directly.
• Safer: no repeated indexing like seq[i].
• Idiomatic: this is the Python way.

What enumerate returns

It returns an iterator that yields (index, value) pairs. It’s lazy and memory-efficient:

1
2
3

it = enumerate(["a", "b", "c"])   # type: enumerate[str]
next(it)  # (0, "a")
next(it)  # (1, "b")

1
2
3
4

it = enumerate(["a", "b", "c"])  # Creates iterator
next(it)  # Returns (0, "a") - first iteration
next(it)  # Returns (1, "b") - second iteration  
next(it)  # Would return (2, "c") - third iteration

1
2
3
4
5
6
7

# This does the same thing automatically
for index, value in enumerate(["a", "b", "c"]):
    print(index, value)
# Output:
# 0 a
# 1 b  
# 2 c

Property start

1
2
3
4
5

numlist = [4, 5, 6]

for index, value in enumerate(numlist, start=1):
    print(index, value)

enumerate(..., start=1) only changes the counter it yields; it does not change how the list is indexed.

• The list numlist = [4, 5, 6] still has real indices 0→4, 1→5, 2→6.
• With start=1, enumerate will report pairs (1, 4), (2, 5), (3, 6), but the underlying list is still 0-based.

dict

1

index_of: dict[int,int]={}

Python dictvs list(as Array) - Core Concepts & Structure

Key Characteristics of dict

• Key-Value Pairs: Stores data as unique keys mapped to values. Think of it like a phone book (key=name, value=number).
• Efficiency: Optimized for fast lookups by key. Underlying implementation uses a hash table.
• Mutability: we can change, add, or remove key-value pairs after creation.
• Key Uniqueness: If a key is used again, the previous value is overwritten.
• Syntax: Created with curly braces {}. person = {"name": "Alice", "age": 30, "city": "London"}

Key Characteristics of list(as a String Array)

• In Python, the listis the primary data structure used as a flexible "array" that can hold items of any type, including strings.
• Ordered Collection: Elements are stored in a specific sequence.
• Index-Based Access: The first element is at index 0, the second at 1, and so on.
• Mutability: we can change, add, or remove elements after creation.
• Syntax: Created with square brackets []. fruits_list = ["apple", "banana", "orange"] # A list of strings

When to Use Which?

• Use a dict when we need to label and associate data. Each item has a unique name (key) that holds a specific value. Perfect for structured data like a user profile ('name', 'id', 'email').
• Use a list when we have a simple, ordered collection of items of the same kind, and we care about their sequence. Ideal for lists of names, tasks, or any sequence where position matters.

dict.get is a safe dictionary lookup. It returns the value for a key if present; otherwise it returns a default (which is None if you don’t supply one). It also avoids raising KeyError.

dict.get

1

value = mapping.get(key, default=None)

• If key exists → returns mapping[key].
• If key is missing → returns default (or None if we didn’t pass one).

In this snippet:

1

j = index_of.get(complement)

• index_of is dict[int, int].
• j will be int | None.
• We then check if j is not None and j != i: to confirm we found a distinct index.

Why use get here?

• It’s one operation (hash lookup) that either gives we the value or None.
• If we used if complement in index_of: j = index_of[complement], we’d typically do two lookups (membership test, then indexing).

Important pitfall

Do not write if j: — index 0 is a valid result but is “falsy” in Python. Use is not None (or test membership first).