[Two Pointers] 3Sum

3Sum Problem

Statement

Given an integer array nums, find and return all unique triplets [nums[i], nums[j], nums[k]], where the indexes satisfy i≠j, i≠k, and j≠k, and the sum of the elements nums[i] + nums[j] + nums[k] == 0.

Constraints

• 3≤ nums.length ≤500
• −10^3≤ nums[i] ≤10^3

Approaches

* All numbers in the array are positive, so it is impossible to find any combination of three numbers that addes up to zero.

 

1. Sort the input array in ascending order. Declare an empty array for the results.

2. Iterate over the input array. While iterating, if the current element is greater than zero or ypu have reached the end of the array, terminate the loop and return the result.

3. If the current value in the iteration is the same as the previous value, skip the iteration.

4. Use two pointers (low and high) for each iteration to find pairs that sum to zero along with the current element.

5. If the sum is less than zero, move low forward. If the sum is grater than zero, move high backward.

6. If the sum equals zero, add the triplet to the result and adjust both pointers.

 

1. 배열 정렬 nums.sort()

2. 반복문을 사용하여 배열 순회. 배열은 순회하면서 첫 번째 숫자 nums[i]를 선택. (고정된 첫 번째 숫자를 선택한 후, 나머지 두 개를 찾기 위해 투 포인터 사용 for i in range(len(nums))

3. nums[i] > 0 이면 반복 종료. 배열이 정렬된 상태에서 nums[i]>0 이면 더 이상 0을 만들 방법이 없으므로 즉시 종료 if nums[i]>0: break. 첫 번째 숫자가 양수인 경우, 뒤의 low, high 숫자도 양수이므로 더 이상 0을 만들 수 없음

4. 같은 숫자가 연속으로 나오는 경우 중복된 결과를 방지하기 위해 스킵 if i>0 and nums[i] == nums[i-1]: continue

5. 두 개의 포인터 (low, high) 설정. low = i+1(현재 숫자 바로 다음), high = len(nums)=1(배열의 끝). low , high = i+1, len(nums)-1

6. 투 포인터로 합이 0인지 확인. 세 가지 경우: 

    합이 0보다 작으면 low += 1 : 더 큰 값이 필요함

    합이 0보다 크면 high -= 1 : 더 작은 값이 필요함

    합이 0이면 결과 리스트에 추가

7. 중복된 값 건너뛰기. 같은 값이 연속으로 나오는 경우 중복 결과 방지

8. 포인터 이동

 

Solution

Using the two pointers pattern to solve the problem. This method requires sorting the input array, so our first step is sorting the array. Sorting the array facilitates the two-ponters technique and makes it easy to handle duplicate balues. As duplicate values are next to each other in a sorted array, we can skip over them to ensure the result contains unique triplets. Once the array is sorted, we iterate over it. For each iteration, we select a "pivot" element nums [i] and focus on the elements to the right of it. The goal is to find all parie of numbers that sum to -nums[i]. Adding this pair to the pivot ensures the total sum equals zero.

The two pointers approach involves positioning one pointer just after the pivot(low) and the other at the array's end(high). By computing the sum of these pointers and the pivot, adjustments are made: increamenting 'low' if the sum is too small or decrementing high if it is too large. When the sum equals zero, the triplet is added to the result, and both pointers are adjusted, skipping duplicates. This strategy focuses on efficient explorationm guiding the sum toward zero.

 

1. Sorting the input array, nums, in ascending order.

2. Create an empty list, result, to store the unique triplets.

3. Use a for loop to iterate over the array, treating each element nums[i]  as the pivot.

4. Start the iteration at index 0 until the third-to-last element (because at least three elements are needed for a triplet).

   Initialize two pointers: 

     low starts at i+1 (the element after the pivot).

     hight starts at the last element of the array.

  While low is less than high, compute the sum of the pivot, nums[low], and nums[high]:

     If the sum is less than zero, increment low to increase the sum.

     If the sum s greater than zero, decrement high to decrease the sum.

     If the sum equals zero:

       Add the triplet [nums[i], nums[low], nums[high]] to the result.

       Move both pointers to their next positions (low++ and high--).

       Skip duplicates at the new low and high positions to ensure unique triplets.

  If nums[i] is the same as nums[i-1] (for i> 0), skip the current iteration.

  If nums[i]>0, break the loop.

5. Once the loop completes, return the result list containing all unique triplets.

 

def three_sum(nums):
  
  # Replace this placeholder return statement with your code
  nums.sort()
  result = []
  for i in range(len(nums)):
    if nums[i] > 0:
      break
    if i > 0 and nums[i] == nums[i-1]:
      continue
    
    low , high = i+1, len(nums)-1

    while low < high:
      sum =  nums[i] + nums[low] + nums[high]
      if sum < 0:
        low += 1
      elif sum > 0 :
        high -= 1
      elif sum == 0:
        result.append([nums[i], nums[low], nums[high]])
        
        while low < high and nums[low] == nums[low + 1]:
          low += 1
        while low < high and nums[high] == nums[high - 1]:
          high -= 1
        low += 1
        high -= 1
        
  return result

 

def three_sum(nums):
    # Sort the array
    nums.sort()
    result = []
    n = len(nums)

    # Iterate through the array
    for pivot in range(n):
        # If the current number is greater than 0, break the loop (no valid triplets possible)
        if nums[pivot] > 0:
            break
        # Skip duplicate values for the pivot
        if pivot > 0 and nums[pivot] == nums[pivot - 1]:
            continue
        
        # Use two-pointer technique
        low, high = pivot + 1, n - 1
        while low < high:
            total = nums[pivot] + nums[low] + nums[high]
            if total < 0:
                low += 1
            elif total > 0:
                high -= 1
            else:
                # Found a triplet
                result.append([nums[pivot], nums[low], nums[high]])
                low += 1
                high -= 1
                # Skip duplicates for low and high pointers
                while low < high and nums[low] == nums[low - 1]:
                    low += 1
                while low < high and nums[high] == nums[high + 1]:
                    high -= 1

    return result

 

Time complexity: O(n²)

The time complexity of the algorithm is O(n²)

- Sorting: The sort() function takes O(nlogn)

- Two pointers: The dominant factor is the nested iteration, where each pivot element is paired with a two pointers tracerasl over the remaining elements of the array. For larger arrays, this results in an O(n²) complexity.

  1. for loop: O(n)

  2. Two pointer: O(n)

  => O(n) * O(n) = O(n²)

두 개의 시간 복잡도에서 지매적인 시간 복잡도는 O(n²)

 

Space Complexity: O(n)

1. Sorting: The sort() function uses O(n) auxiliary space for its operations.

2. Two pointers and result storage: The two pointer approach operates in place, and the result storage depends on the number of triplets, which is generally mush smaller than the input size.

  Two pointers operates in place: 두 포인터는 별도 메모리를 사용하지 않고 in-place 동작 => O(1)

  The result storage depends on the number of triplets: 결과 저장 공간은 찾은 세 수의 조합 개수에 의존 => O(k) k<<n (n 보다 훨씬 작음). 일반적으로 결과 크기는 입력 크기보다 훨씬 작음 

 

추가 학습사항

퀵 정렬 (Quick Sort) ->  평균 O(n log n)

병합 정렬 (Merge Sort) -> O(n log n)

파이썬 Sort() (Timsort) -> 최악의 경우 O(n log n), 최선의 경우 O(n)

   Timsort는 병합정렬 + 삽입 정렬을 결합한 하이브리드 알고리즘

   1. 최악의 경우에도 O(n log n) : 안정적인 성능

   2. 최선의 경우 O(n) : 이미 정렬된 배열에서 매우 빠름

   3. 실제 데이터에서 매우 효율적: 정렬된 부분 배열을 활용

   4. 안정 정렬(Stable Sort): 같은 값의 상대적 순서를 유지. 동일한 값(같은 키)을 가진 요소들이 정렬 후에도 원래 순서를 유지하는 정렬 알고리즘. 같은 값을 가진 요소들이 정렬되더라도 원래의 상대적인 순서(order)는 그래도 유지됨. 데이터의 원래 순서를 유지하면서 정렬해야 할 때 유용. 정렬 후에도 동일한 값의 기존 순서가 유지되므로 정렬된 데이터의 구조를 보

   5. 빠르고 메모리 사용이 효율

 

정렬 알고리즘은 비교 기반 정렬(Comparison-based Sorting)을 사용

1. 각 원소를 비교하는 데 걸리는 시간 O(log n)

- 대부분의 정렬 알고리즘은 재귀적으로 문제를 반으로 나누는 방식을 사용

- 한 번 비교할 때마다 배열을 반으로 줄이므로 log n 단계가 필요함

2. 배열 전체를 정렬하는 데 걸리는 시간 O(n)

- 정렬을 수행하려면 모든 n개의 원소를 적어도 한 번씩은 확인해야 함.

- 따라서 각 log n 단계마다 n개의 원소를 정렬하는 작업이 포함

∴ O(n log n)