[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 we 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).

Approach 3: one-pass hash table

One-pass Two Sum: scan once with a dict mapping value → index. For each x at i, compute y = target - x; if y is in the dict, return [index_of[y], i], else store index_of[x] = i. Use enumerate for (i, x). Time: O(n) (amortized), Space: O(n). A thin Solution.twoSum method just delegates to the typed, PEP-8 two_sum function.

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
44
45

from __future__ import annotations


def two_sum(nums: list[int], target: int) -> list[int]:
    """Return indices [i, j] such that nums[i] + nums[j] == target.

    One-pass hash table:
      * Scan left→right once.
      * For each value x at i, compute y = target - x.
      * If y has been seen earlier (in a dict), return its index and i.
      * Otherwise remember x -> i and continue.

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

    Returns:
        Two indices [j, i] (order not important). Empty list if not found.
    """
    index_of: dict[int, int] = {}  # value -> index

    for i, x in enumerate(nums):
        y = target - x
        if y in index_of:              # O(1) average-time membership check
            return [index_of[y], i]    # earlier index, current index
        index_of[x] = i                # remember current value's index
    return []


class Solution:
    """LeetCode adapter (method name must be `twoSum`)."""

    def twoSum(self, nums: list[int], target: int) -> list[int]:
        return two_sum(nums, target)


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


if __name__ == "__main__":
    main()

Function inside vs outside the class -> self

1
2
3
4
5
6

def two_sum(nums: list[int], target: int) -> list[int]:
...
class Solution:
    """LeetCode adapter (method name must be `twoSum`)."""

    def twoSum(self, nums: list[int], target: int) -> list[int]:

Why do we put two_sum outside the Solution

• Stateless logic ⇒ module-level function. Google’s Python style (and most “serious” codebases) prefer a plain function when code doesn’t need object state. Don’t create classes/methods unless we need them.
• Testability & reuse. A top-level two_sum(...) is easy to import, unit-test, and reuse anywhere. The Solution class is just a LeetCode quirk.
• PEP 8 naming. At module level we can use proper snake_case. The LeetCode method name twoSum is camelCase because the platform requires it.

With slef vs without self

1
2
3
4
5
6

def two_sum(nums: list[int], target: int) -> list[int]:
...
class Solution:
    """LeetCode adapter (method name must be `twoSum`)."""

    def twoSum(self, nums: list[int], target: int) -> list[int]:

• Top-level function (defined outside a class) has no implicit object, so no self.
• Instance method (defined inside a class, without decorators) is called on an instance; Python automatically passes that instance as the first argument. By convention we name it self.

Explanation

When we write:

1
2
3
4
5
6
7

class Accumulator:
    def __init__(self, total: int = 0) -> None:
        self.total = total

    def add(self, x: int) -> int:
        self.total += x
        return self.total

and call:

1
2

acc = Accumulator(10)
acc.add(5)

Python rewrites acc.add(5) to:

1

Accumulator.add(acc, 5)

So self is just the instance (acc) that’s implicitly supplied. That’s why an instance method signature must accept a first parameter—by convention named self.

When we need (or don’t need) self

• We need self when the method uses instance state or calls other instance methods:

  1 2 3 4 5 6 7

  class Counter: def __init__(self, start: int = 0) -> None: self.count = start def inc(self, step: int = 1) -> int: self.count += step return self.count

• We don’t need self if the logic doesn’t touch instance or class state. Use a top-level function or a @staticmethod:

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

  def two_sum(nums: list[int], target: int) -> list[int]: index_of: dict[int, int] = {} for i, x in enumerate(nums): y = target - x if y in index_of: return [index_of[y], i] index_of[x] = i return [] class Solution: @staticmethod def twoSum(nums: list[int], target: int) -> list[int]: return two_sum(nums, target)

• If the method needs the class (not an instance)—e.g., alternate constructors or class-wide config—use @classmethod and name the first parameter cls.

Why the outside function doesn’t need self

A top-level function like:

1

def two_sum(nums: list[int], target: int) -> list[int]: ...

isn’t bound to any object. There’s no instance to pass, so no self parameter.

Rule of thumb:

• Put pure, stateless logic at module level (no self).
• Use instance methods (with self) when we need per-object state.
• Use @staticmethod or @classmethod when appropriate.

dict used in if

1
2

if y in index_of:
    return [i, index_of[y]]

This checks membership of the key (not values) in the dict.

• True if we have already seen y earlier and stored it as a key.

• Dict membership is amortized O(1).

• If found, return the pair of indices. (Either [index_of[y], i] or [i, index_of[y]] is fine for LeetCode.)

others

1

return []

• Defensive fallback. LeetCode guarantees a solution; outside LeetCode, this makes the function total (never implicitly returns None).

1
2

def main() -> None: ...
if __name__ == "__main__": main()

• Standard script entry-point guard. Runs main() only when this file is executed directly, not when imported.

Complexity

• Time: O(n) average (each step does O(1) dict operations).
• Space: O(n) (worst case store almost all elements before finding the pair).

Common gotchas

index_of.get vs index_of[]

statement

Between the two idioms, the single-lookup .get() pattern is safest and usually a bit faster. Direct indexing (d[key]) can raise KeyError when the key is missing; combining key in d and d[key] is safe but does two lookups. All variants are O(n) overall; differences are constant-factor only.

Given two one-pass Two Sum snippets, is there a speed/behavior difference?

1
2
3
4
5
6
7
8

# A) single lookup (recommended)
j = index_of.get(nums_complement)
if j is not None and j != i:
    return [i, j]

# B) membership + indexing (also OK)
if nums_complement in index_of and index_of[nums_complement] != i:
    return [i, index_of[nums_complement]]

Why does index_of[nums_complement] is not None sometimes error?

Analysis

• Direct indexing index_of[nums_complement]:
  • If the key is absent, Python immediately raises KeyError—we never reach the is not None check.
• .get() (index_of.get(nums_complement)):
  • Returns the value or None when missing (no exception).
  • Lets we safely write if j is not None:. (Use is not None because index 0 is valid but falsy.)
  • One lookup per iteration.
• in + indexing (key in d and d[key]):
  • Safe due to short-circuiting, but performs two lookups (membership, then indexing).
• Performance:
  • All approaches keep the algorithm O(n).
  • .get() typically has the best constant factor (one hash probe).
  • in + [] doubles lookups; using exceptions for flow control is slower.

Case explanation

Mini examples show behavior:

1
2
3
4
5
6
7
8
9
10
11

d: dict[int, int] = {7: 1}

# Direct indexing — raises on missing keys
# d[2]         # KeyError

# Safe single lookup
j = d.get(2)   # None

# Membership + indexing (safe but two lookups)
if 7 in d and d[7] != 0:
    pass

Applied to Two Sum (concise, typed):

1
2
3
4
5
6
7
8
9
10
11

from __future__ import annotations

def two_sum(nums: list[int], target: int) -> list[int]:
    index_of: dict[int, int] = {}
    for i, x in enumerate(nums):
        y = target - x
        j = index_of.get(y)             # single safe lookup
        if j is not None and j != i:    # handle index 0 correctly
            return [j, i]
        index_of[x] = i
    return []

Takeaway: Prefer the .get() single-lookup pattern for clarity, safety (no KeyError), and slightly better performance.

Addendum: why and works here, but .get() is still preferable

Snippet

1

if nums_complement in index_of and index_of[nums_complement] != i:

is safe because Python’s and short-circuits:

• It first evaluates nums_complement in index_of (membership on keys).
• Only if that is True does it evaluate index_of[nums_complement] != i. This prevents a KeyError when the key is missing.

So it runs normally. The tradeoff is performance: when the key is present, we’ve done two hash lookups (one for in, one for []). The single-lookup pattern avoids that extra work:

1
2
3

j = index_of.get(nums_complement)   # one lookup
if j is not None and j != i:
    return [i, j]

Use .get() when we can—it’s clearer, avoids KeyError, handles index 0 correctly with is not None, and typically has a slightly better constant factor.

Conventions

1. If function inside a class then the name of it should like twoSum if outside a class it will be two_sum