Algorithm to count unique values in the array using the Multiple-Pointers pattern, used two approach-CodePudding

The question was to implement a function called countUniqueValues, which accepts a sorted array, and counts the unique values in the array. There can be negative numbers in the array, but it will always be sorted.

I used the Multiple Pointers Pattern to solve this question so that it has time complexity of O(n) and space complexity of O(1). I used two different approaches, one with a for loop and one with a while loop.

Which of these approaches is better?

Approach 1: Using for loop

function countUniqueValues(arr) {
  if (arr.length === 0) return 0;

  let pointer1 = 0;

  for (let pointer2 = 1; pointer2 < arr.length; pointer2  ) {
    if (arr[pointer1] !== arr[pointer2]) {
      pointer1  ;
      arr[pointer1] = arr[pointer2];
    }
  }

  return pointer1   1;
}

Approach 2: Using while loop

function countUniqueValues(arr) {
  if (arr.length === 0) return 0;

  let pointer1 = 0;
  let pointer2 = pointer1   1;
  
  while (pointer2 < arr.length) {
    if (arr[pointer1] !== arr[pointer2]) {
      pointer1  ;
      arr[pointer1] = arr[pointer2];
      pointer2  ;
    } else if (arr[pointer1] === arr[pointer2]) {
      pointer2  ;
    }
  }
  
  return arr.slice(0, pointer1   1).length;
}

Expected Time Complexity: O(n)
Expected Space Complexity: O(1)

CodePudding user response：

Using for instead of while loop with exactly the same idea is not a different approach.

The logic is correct but it could have been way simpler. You want to find the those positions in arrays where the elements are different (borders). Now your final answer is <#border> 1.

    let border = 0;
    for (let i = 1; i < arr.length; i  ) {
        if (arr[i - 1] != arr[i]) {
            border  ;
        }
    }
    return border 1;

You do not need to change the array, you do not need to keep two pointers.