Algorithms & Arrays

Python Two Sum (Optimal Hash Map)

Find two indices in an array whose values sum to a specific target in optimal O(N) linear time using a hash map lookup.

Python Source Code

Editable code sample with line numbers

Python

Expected Output

When this program is compiled and executed, the terminal outputs:

Array: [2, 7, 11, 15]
Target: 9
Result Indices: [0, 1] (Values: 2 + 7 = 9)

How the Code Works

By storing previously seen values and their indices in a dictionary (hash table), we can check for the existence of the complement (target - num) in O(1) average time per element.

Time Complexity

O(N)

Space Complexity

O(N)

Key Takeaways & Best Practices

Hash table complement lookup eliminates the nested O(N^2) brute force loop.
enumerate() supplies both element index and value in Python loops.

Master Python with ZenCompiler

Practice in our high-performance cloud container IDE with multi-file support, interactive terminal STDIN, real-time memory visualizer, and structured lessons.

Related Python Examples

Math & Numbers

O(√N)

Python Program to Check Prime Number

A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself. This example demonstrates an optimized approach checking factors up to √n.

Python Program for Fibonacci Series

The Fibonacci sequence is a series where each number is the sum of the two preceding ones, starting from 0 and 1. Here we implement iterative generation and generator streaming.