iOS Interview - Leetcode 15. 3 Sum

July 23, 20242 min read#swift, #interview, #leetcode

Leetcode: 15. 3 Sum

  • Primary idea: use the Two Pointers to find the remaining 2 indexes that fulfil the requirement
  • Time Complexity: O(n^2)
  • Space Complexity: O(n)
func threeSum(_ nums: [Int]) -> [[Int]] {
    var nums = nums.sorted()
    var result = Set<[Int]>() // (Optional) Use Set to avoid duplicated results
    
    for i in 0..<nums.count {
        // Stop processing since the sum will always be positive.
        if nums[i] > 0 {
            break
        }
        
        // Ignore duplication
        if i > 0 && nums[i] == nums[i - 1] {
            continue
        }
        
        // 2 pointers to search for indexes from left and right sides of the sorted array
        var left = i + 1
        var right = nums.count - 1
        
        while left < right {
            let sum = nums[i] + nums[left] + nums[right]
            
            if sum == 0 {
                result.insert([nums[i], nums[left], nums[right]])
                
                // Ignore same numbers from the left to avoid duplicated results
                while left <  right && nums[left] == nums[left + 1] {
                    left += 1
                }
                
                // Ignore same numbers from the right to avoid duplicated results
                while left < right && nums[right] == nums[right - 1] {
                    right -= 1
                }
                
                left += 1
                right -= 1
            } else if sum < 0 {
                left += 1
            } else {
                right -= 1
            }
        }
    }
    
    return Array(result)
  }
  
  print(threeSum([0,1,1])) // []
  print(threeSum([0,0,0])) // [[0, 0, 0]]
  print(threeSum([-1,0,1,2,-1,-4])) // [[-1, -1, 2], [-1, 0, 1]]
  print(threeSum([2,0,-2,-5,-5,-3,2,-4])) // [[-4,2,2],[-2,0,2]]

Futher readings:

Quick Drop logo

Profile picture

Personal blog by An Tran. I'm focusing on creating useful apps.
#Swift #Kotlin #Mobile #MachineLearning #Minimalist


© An Tran - 2024