Editorial for Two Sum


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Scan left to right while storing previously seen values in a hashmap:

  • At index j, the needed partner value is target - a[j].
  • If that value is already in the hashmap at index i, output i + 1 and j + 1.
  • Otherwise, store a[j] with its index and continue.

Because each lookup and insert is O(1) on average, total time complexity is O(n).

Solution (Python)

n, target = (int(x) for x in input().split())
a = [int(x) for x in input().split()]

seen: dict[int, int] = {}

for i in range(n):
    need = target - a[i]
    if need in seen:
        print(seen[need] + 1, i + 1)
        break
    seen[a[i]] = i

Comments

There are no comments at the moment.