Finding indices of array elements that add up to a target number. What would be a way to optimize my solution?

user_18560932 0
Viewed 838

I'm practicing this problem

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

and came up with

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var indices = [Int]()
        
        for (firstIndex, firstNum) in nums.enumerated() {
            for (secondIndex, secondNum) in nums.enumerated() {
                if firstNum + secondNum == target && firstIndex != secondIndex {
                    indices = [firstIndex, secondIndex]
                }
            }
        }
        
        return indices
    }
}

However, it has quadratic time complexity because of the nested for-in loops. What would be a good way to optimize this to run in linear time?

swift data-structures algorithm
3 Answers

Here's an idea that results in a O(n) time ans space solution.

  1. Have a hashtable that maps elements to their indices.
  2. As you iterate through the input array check whether target - element is in the hashtable already. If so, return the indices of the current element and target - element in the hashtable.
  3. If not, add current element as key and its index as value to the hashtable.
user_77556650

Using @user1984 comment your solution should look like this:

 class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var indices = [Int]()
        var dictionary: [Int: Int] = [:] 
        for (index, num) in nums.enumerated()  
           { 
             let diff = target - num  
             if let index2 = dictionary[diff]  {
                  return [index2, index] 
                }
             else {
                 dictionary[num] = index 
                }
           }
       return []
       }
 }
user_85287710

There are several approaches (depending on your requirements and time/space constraints)

final class Solution {
    
    // Time Complexity: O(n * (n - 1) / 2) = O(n^2)
    // Auxiliary Space: O(1)
    
    func twoSum1(_ nums: [Int], _ target: Int) -> [Int] {
        for firstIndex in nums.indices {
            for secondIndex in (firstIndex + 1)..<nums.count {
                if nums[firstIndex] + nums[secondIndex] == target {
                    return [firstIndex, secondIndex]
                }
            }
        }
        
        return []
    }
    
    // Time Complexity: O(n log n).
    // Auxiliary Space: O(n). Can be O(1) if do in-place sort
    
    func twoSum2(_ nums: [Int], _ target: Int) -> [Int] {
        let sorted = nums.sorted()
        
        var left = 0
        var right = nums.count - 1
        
        while left < right {
            if sorted[left] + sorted[right] == target {
                return [left, right]
            } else if sorted[left] + sorted[right] < target {
                left += 1
            } else {
                right -= 1
            }
        }
        
        return []
    }
    
    // Time Complexity: O(n). (Amortized)
    // Auxiliary Space: O(n).
    
    func twoSum3(_ nums: [Int], _ target: Int) -> [Int] {
        var differences = [Int: Int]()
                
        for (index, element) in nums.enumerated() {
            let difference = target - element
            
            if let dIndex = differences[difference] {
                return [index, dIndex]
            }
            
            differences[element] = index
        }
        
        return []
    }
    
    static func test() {
        // Given
        let nums = [1, 5, 4, 3, 7, 9, -3]
        let target = 7

        let solution = Solution()
        let expectedResult = [2, 3]
        
        // When
        let result1 = solution.twoSum1(nums, target)
        let result2 = solution.twoSum2(nums, target)
        let result3 = solution.twoSum3(nums, target)

        // Then
        assert(Set(result1) == Set(expectedResult))
        assert(Set(result2) == Set(expectedResult))
        assert(Set(result3) == Set(expectedResult))
    }
}
user_142945610
Related