Solving the ‘Two Sum Problem’ on LeetCode — PHP Solutions Walkthrough

Image Source

Introduction

In this post, we will delve into three distinct solutions to the Two Sum Problem, this time using PHP. By contrasting their time and space complexities, we’ll understand which method offers optimal performance. A comprehensive, step-by-step breakdown with annotated code for each solution follows the conclusion.

Problem Description

Given an array of integers nums and an integer target, return the indices of the two numbers that sum up to the target.

Function Prototype:

function twoSum(array $nums, int $target): array;

Example 1:

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

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Solution 1: Brute Force Approach

This method utilizes two loops to go through each possible pair of numbers to find the desired sum.

PHP Code:

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
  function twoSum(array $nums, int $target): array {
    for($i = 0; $i < count($nums); $i++) {
        for($j = $i + 1; $j < count($nums); $j++) {
            if($nums[$i] + $nums[$j] == $target) {
                return [$i, $j];
            }
        }
    }
    return [];
    }
}

Time Complexity: O(n²), The outer loop runs n times, and for each iteration of the outer loop, the inner loop runs n - 1, n - 2, ..., 1 times. The sum of this arithmetic series approaches n^2/2, which is O(n²) in big O notation.
Space Complexity: O(1), This approach does not use any additional data structures whose size depends on the input size. Only a constant amount of extra space is used for variables.

Solution 2: Sorting and Two Pointers Approach

This technique sorts the array first and then uses two pointers to locate the two numbers.

PHP Code:

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
   function twoSum(array $nums, int $target): array {
    $indices = range(0, count($nums)-1);
    array_multisort($nums, $indices);
    
    $left = 0;
    $right = count($nums) - 1;
    
    while($left < $right) {
        $sum = $nums[$left] + $nums[$right];
        if($sum == $target) {
            return [$indices[$left], $indices[$right]];
        } elseif($sum < $target) {
            $left++;
        } else {
            $right--;
        }
    }
    return [];
    }
}

Time Complexity: O(n log n), Sorting the array takes O(n log n) time, which dominates the time complexity. After sorting, the two-pointer technique runs in O(n) time because each of the two pointers runs through the list at most once.
Space Complexity: O(n), The space complexity is primarily due to storing the original indices of the numbers in the $indices array. This requires linear, or O(n), space.

Solution 3: Associative Array Approach

In PHP, we can use associative arrays, which act similarly to hash maps in other languages.

PHP Code:

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
   function twoSum(array $nums, int $target): array {
    $map = [];
    for($i = 0; $i < count($nums); $i++) {
        $complement = $target - $nums[$i];
        if(isset($map[$complement])) {
            return [$map[$complement], $i];
        }
        $map[$nums[$i]] = $i;
    }
    return [];
    }
}

Time Complexity: O(n), The function goes through the list of numbers only once, with each lookup in the associative array (or map) taking constant time on average.
Space Complexity: O(n), In the worst-case scenario, the associative array (or map) might end up storing every number from the list, leading to O(n) space complexity.

Conclusion and Comparison

Each of the methods described above has its own set of advantages and drawbacks when tackling the “Two Sum” problem using PHP:

Brute Force Approach:

• Pros: It’s straightforward and does not demand any extra data structures or advanced coding techniques.
• Cons: Its O(n²) time complexity makes it the least efficient for larger datasets, potentially causing substantial delays.

Sorting and Two Pointers Approach:

• Pros: Once the array is sorted, searching for the numbers becomes more systematic. This method is markedly faster than the brute force technique.
• Cons: Sorting the array results in the loss of original indices. This is addressed by tracking the indices separately. The space complexity also slightly increases due to this extra storage.

Associative Array Approach:

• Pros: Highly time-efficient with an O(n) time complexity. This approach requires just one pass through the array, making it the best choice for larger datasets.
• Cons: This method needs extra space due to the associative array which can store all elements from the list.

Choosing the right method hinges on balancing time and space complexity. For the “Two Sum” problem in PHP, the Associative Array Approach proves most efficient, especially for larger datasets.

1. Two Sum — LeetCode
2. PHP Documentation

Thank you for reading! If you find this guide helpful, please consider highlighting, clapping, responding or connecting with me on Twitter/X as it’s very appreciated!

Also check out my other Leetcode Walkthrough Lists:

• Palindrome Number Problem

Step-by-Step Explanations with Code Comments

Solution 1: Brute Force Approach with Comments

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
   function twoSum(array $nums, int $target): array {
    // Step 1: Start the first loop to iterate over each number in the array.
    for($i = 0; $i < count($nums); $i++) {
        // Step 2: Begin the second loop to go through the numbers following the current one.
        for($j = $i + 1; $j < count($nums); $j++) {
            // Step 3: Check if the current pair of numbers add up to the target.
            if($nums[$i] + $nums[$j] == $target) {
                return [$i, $j];
            }
        }
    }
    // Step 4: If no such pair is identified, return an empty array.
    return [];
    }
}

• Step 1: The initial loop starts, focusing on every individual number in the provided array.
• Step 2: A secondary loop commences, which reviews the numbers positioned after the number identified by the outer loop.
• Step 3: If the combination of the numbers from the two loops equals the target, their indices are returned.
• Step 4: Should no such pair be detected, an empty array is produced.

Solution 2: Sorting and Two Pointers Approach with Comments

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
   function twoSum(array $nums, int $target): array {
    // Step 1: Track the original indices.
    $indices = range(0, count($nums)-1);
    
    // Step 2: Sort the numbers while preserving their original indices.
    array_multisort($nums, $indices);
    
    $left = 0;
    $right = count($nums) - 1;
    
    // Step 3: Use two pointers, one at the start and another at the end.
    while($left < $right) {
        $sum = $nums[$left] + $nums[$right];
        // Step 4: If the numbers at the two pointers add up to the target, return their    original indices.
        if($sum == $target) {
            return [$indices[$left], $indices[$right]];
        } elseif($sum < $target) {
            $left++;
        } else {
            $right--;
        }
    }
    // Step 5: If no suitable pair is found, return an empty array.
    return [];
    }
}

• Step 1: All original positions of the numbers are tracked.
• Step 2: The numbers are sorted, but their initial positions remain tracked.
• Step 3: Two pointers are deployed: one at the array’s beginning and another at its end.
• Step 4: If the numbers at the two pointer locations add up to the target, their primary positions are returned.
• Step 5: If no match is identified, an empty array is produced.

Solution 3: Associative Array Approach with Comments

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
   function twoSum(array $nums, int $target): array {
    // Step 1: Initialize an associative array for fast lookups.
    $map = [];
    
    // Step 2: Go through each number in the array.
    for($i = 0; $i < count($nums); $i++) {
        $complement = $target - $nums[$i];
        // Step 3: If the complement is found in the array, return its index along with the current number's index.
        if(isset($map[$complement])) {
            return [$map[$complement], $i];
        }
        // Step 4: If not, add the current number and its index to the associative array.
        $map[$nums[$i]] = $i;
    }
    // Step 5: If no matching pair is located, return an empty array.
    return [];
    }
}

• Step 1: An associative array, often termed as a map in other languages, is initiated for rapid data lookups.
• Step 2: The entire list of numbers is iterated through.
• Step 3: For every number, if its complement (the number that, when added to the current number equals the target) is found in the map, then the positions of both the current number and its complement are returned.
• Step 4: If the complement isn’t in the map, the current number and its index are saved in the map for subsequent lookups.
• Step 5: Should no two numbers be found that combine to reach the target, an empty array is produced.