In this tutorial, we'll explore how to solve the Two Sum problem using the Rust programming language. The Two Sum problem is a classic algorithmic problem often asked in technical interviews. The goal is to find two numbers in an array that add up to a specific target. We'll go over the problem statement, provide a step-by-step solution, and review best practices.

Problem Statement

Given an array of integers, return the indices of the two numbers such that they add up to a specific target.

Example:

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

Assumptions:

  • There is exactly one solution, and you cannot use the same element twice.
  • You can return the answer in any order.

Approach 1: Brute Force

The simplest way to solve the problem is by using a brute force approach, where we check all pairs of numbers and return the indices of the pair that adds up to the target.

Steps:

  1. Use two nested loops to go through all the pairs in the array.
  2. For each pair, check if their sum equals the target.
  3. If it does, return their indices.

Code Implementation:

fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    for i in 0..nums.len() {
        for j in i+1..nums.len() {
            if nums[i] + nums[j] == target {
                return vec![i as i32, j as i32];
            }
        }
    }
    vec![]  // Return an empty vector if no solution is found
}

Explanation:

  • We iterate through the list using two loops.
  • The outer loop picks the first number, and the inner loop picks the second number.
  • If the sum matches the target, the indices of the two numbers are returned.

Time Complexity:

  • Time Complexity: O(n^2) – For every element, we go through the rest of the array, which makes this a quadratic solution.
  • Space Complexity: O(1) – We only use constant extra space.

Approach 2: HashMap for Better Efficiency

The brute force solution works, but it's inefficient for large arrays. We can improve this using a HashMap to store the numbers and their indices as we iterate through the array. This allows us to check for the required number in constant time, reducing the overall complexity.

Steps:

  1. Create an empty HashMap to store each number and its index.
  2. For each element in the array, compute the complement (i.e., target - current_number).
  3. Check if the complement exists in the HashMap:
    • If it does, return the indices of the current number and the complement.
    • If not, add the current number and its index to the HashMap.

Code Implementation:

use std::collections::HashMap;

fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut map = HashMap::new();
    
    for (i, &num) in nums.iter().enumerate() {
        let complement = target - num;
        
        if let Some(&index) = map.get(&complement) {
            return vec![index as i32, i as i32];
        }
        
        map.insert(num, i);
    }
    
    vec![]  // Return an empty vector if no solution is found
}

Explanation:

  • We use Rust's HashMap to store each number as a key and its index as the value.
  • For each number in the array, we compute the complement needed to reach the target.
  • If the complement exists in the HashMap, we return the indices.
  • If not, we store the current number and its index for future lookups.

Time Complexity:

  • Time Complexity: O(n) – We only need to iterate through the list once, and each lookup in the HashMap takes O(1) on average.
  • Space Complexity: O(n) – We store all the numbers in the HashMap, which uses extra space proportional to the size of the input array.

Edge Cases

While the problem guarantees exactly one solution, you should still account for various edge cases during implementation:

  1. Negative and Positive Numbers:
    The array may contain both negative and positive numbers. Ensure that the solution works for both.

    let nums = vec![-3, 4, 3, 90];
let target = 0;
if let Some(result) = two_sum(nums, target) {
    println!("{:?}", result);  // Output: [0, 2]
}

  2. Duplicate Values:
    The array may contain duplicate values, and the solution should still return the correct indices.

    let nums = vec![3, 3];
let target = 6;
if let Some(result) = two_sum(nums, target) {
    println!("{:?}", result);  // Output: [0, 1]
}

  3. Array with Only Two Elements:
    Since the problem guarantees at least two elements, the array can have exactly two elements, and the solution should still work.

    let nums = vec![1, 4];
let target = 5;
if let Some(result) = two_sum(nums, target) {
    println!("{:?}", result);  // Output: [0, 1]
}

  4. Zeros in the Array:
    If the array contains zeros, the solution should correctly handle the target involving zero.

    let nums = vec![0, 4, 3, 0];
let target = 0;
if let Some(result) = two_sum(nums, target) {
    println!("{:?}", result);  // Output: [0, 3]
}

  5. Large Inputs:
    If the array contains a large number of elements, the hash map approach ensures efficiency even with significant data size.

    let nums: Vec<i32> = (0..100000).collect();
let target = 199999;
if let Some(result) = two_sum(nums, target) {
    println!("{:?}", result);  // Output: [99998, 99999]
}

Best Practices

  • Prefer HashMap Approach: The brute force approach may be easier to understand, but it's inefficient for large input arrays. The HashMap approach is both time-efficient and easy to implement in Rust.
  • Handle Edge Cases: Always consider edge cases such as empty arrays, negative numbers, or arrays with no valid solution.
  • Use Rust’s Built-in Features: Rust’s HashMap is a great tool for this problem, providing fast lookups and ease of use.

Conclusion

The Two Sum problem is an excellent way to practice solving algorithmic challenges with Rust. We first tackled the problem using a brute force approach and then improved the solution by using a HashMap to achieve linear time complexity.

If you're preparing for coding interviews or want to enhance your problem-solving skills, practicing problems like Two Sum will help you develop both your algorithmic thinking and proficiency in Rust.