[Algorithm] Multiple Pointers

Two pointers is really an easy and effective technique which is typically used for searching pairs in a sorted array.

Given a sorted array A (sorted in ascending order), having N integers, find if there exists any pair of elements (A[i], A[j]) such that their sum is equal to X.

즉 특정 컨디션에 따라서, 배열의 시작이나 끝처럼 특정한 방향으로 움직이며 값을 비교하는 패턴이다.

Two Pointers

배열을 받은 뒤, 배열을 돌면서 두 숫자의 합이 0이 되는 값이 담긴 배열을 반환하는 함수를 만드세요.

예를 들어,
sumZero( [-3, -2, -1, 0, 1, 4, 5])면,
-1과 1의 합은 0이므로 [-1, 1]을 반환한다.

// Bad!
function sumZero(array) {
  for(let i=0; i<array.length; i++) {
    for(let j=i+1; j<array.length; j++) {
      if(array[i] + array[j] === 0) {
      	return [array[i], array[j]]
      }
    }
  }
}


// Good!
function sumZero(array) {
  let left = 0;
  let right = array.length - 1;

  while (left < right) {
    const sum = array[left] + array[right];

    if (sum === 0) {
      return [array[left], array[right]];
    } else if (sum > 0) {
      right--;
    } else {
      left++;
    }
  }
}

const arr = [-3, -2, -1, 0, 1, 4, 5];
sumZero(arr);

첫번째 코드를 살펴보면 nested for loop를 사용해서 모든 배열을 비교하기때문에, time complexity는 O(N^2)가 된다. 따라서 두번째 코드에 비해서 비효율적이다.

---

Multiple Pointers

배열을 받은뒤, 배열의 유니크한 값의 개수를 반환하는 함수를 만드세요.

예를들어,
countUniqueValue([1, 1, 2, 3, 4, 4, 5, 5, 5, 7]);면,
유니크한 값은 1, 2, 3, 4, 5, 6이므로, 6을 반환한다.

// My solution: pointer pattern을 사용하지 않음
function countUniqueValue(arr) {
  arr.sort();
  let answer = [];
  for (value of new Set(arr)) {
    answer.push(value);
  }
  return answer.length;
}

// Solution
function countUniqueValue(arr) {
  let i = 0;
  for (let j = 1; j < arr.length; j++) {
    if (arr[i] !== arr[j]) {
      i++;
      arr[i] = arr[j];
    }
  }
  return i + 1;
}

countUniqueValue([1, 1, 2, 3, 4, 4, 5, 5, 5, 7]);