LeetCode #1: Two Sum

To practice my skills using basic data structures, I started solving LeetCode challenges in Rust. To make it more difficult, I sticked to the built-in online editor that doesn’t support IntelliSense — which pushes me to remember both syntax and API

The very first problem is about finding two integers within an unsorted list that sum up to a given value. Naïve solution would be comparing each possible pair leading to complexity O(n²). But it can be done better, right? The problem boils down to finding a complement of each candidate to the target value. If the complement is in the list, the value and its complement are the pair we are looking for.

use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut indices: HashMap<i32, usize> = HashMap::new();

        for (index, num) in nums.iter().enumerate() {
            if let Some(found) = indices.get(&(target - num)) {
                return vec![index as i32, *found as i32];
            } else {
                indices.insert(*num, index);
            }
        }

        panic!("Not Found!");
    }
}

Initially I used two loops to ensure that all complements exist before being checked. But during my second thought, I realized that if the complement Y of X is not yet in the hash map, it would be found later as the complement X of Y. I totally dropped one loop.

The result is amazing in terms of CPU and Memory usage compared to the Python solutions I used to implement such problems. The runtime uses the CPU for just 1ms, compared to 82ms in Python. And it uses only 2.5MiB of memory, unlike Python’s 19.8MiB.