High Level

We'll need to use two binary searches for this problem. At a glance, it may seem like we could just find where our array switches from negative numbers to positive with a single search, but because zero is neither negative nor positive, this implementation would not solve an array with one or more zeros.

As such, we'll use one binary search to find where our negative numbers end from the beginning of the array and another binary search to find where our positive numbers end from the end of our array. Remember, binary search problems depend on the array being sorted; this problem is no exception.

Once we know where our negatives stop and our positives start, we can use those indices to calculate the count of each and return the smaller of the two counts.

Algorithm

We'll create three functions to break our problem into smaller pieces: minimumCount, findFirstPositiveIndex, and findLastNegativeIndex.

The findFirstPositiveIndex function utilizes a binary search algorithm to find the first positive number in the array:

1. Initialize two pointers, left and right, representing the array's start and end, respectively.
2. Initialize firstPositiveIdx to the length of the array, which assumes that all numbers could be negative until proven otherwise.
3. Calculate the middle index, mid.
4. Check if nums[mid] is less than or equal to zero.
   • If it is, we continue searching the right half of the array by setting left to mid + 1.
   • If it is not, meaning it is positive, we set firstPositiveIdx to the value of mid and continue searching the left half of the array by setting right to mid - 1.
5. Continue steps 3 and 4 until left exceeds right. At this point, firstPostiveIdx will point to the first positive number, or it will have never been reassigned and remain as the length of the array, meaning all numbers were negative.

Conversely, findLastNegativeIndex seeks the index of the last negative number in the array, using a similar binary search approach. It starts with left and right pointers and iteratively finds the last index where a negative number exists, denoted by lastNegativeIdx. If the array only contains positive numbers, the function returns -1.

Finally, we will use our third function, minimumCount to utilize our first two functions and find the smaller count:

1. Get lastNegativeIdx from findLastNegativeIndex. The count of negative numbers is the lastNegativeIdx + 1 since indices are zero-based.
2. Get firstPositiveIdx from findFirstPositiveIndex. The count of positive numbers is the total number of elements in the array minus firstPositiveIdx.
3. Return the smaller of the two counts.

Time Complexity

The time complexity of this solution is similar to that of the "Find The Ranges of Three" problem. Because we perform two binary searches, our time complexity is O(2logN). However, we can simplify it to O(logN) by eliminating the constants.

Space Complexity

The space complexity of this algorithm is O(1). The functions don't utilize any extra data structures that grow with the size of the input.

---

Walkthrough

Let's see this visually using an example array [-3, 1, 2, 3, 4, 5].

Part 1 - Finding the Index of the First Positive Value

Step 1: In the first step, we are initializing two pointers, left and right, at indices 0 and 5 respectively, and the firstPositiveIdx to 6, assuming that all numbers in the array are negative until proven otherwise.

Step 2: In the second step, we calculate the middle index using the formula ((0 + 5) / 2), which results in 2 rounded down. Since the number at this index is positive, we reassign firstPositiveIdx to 2, and move to the left, by reassigning right to mid - 1.

Step 3: In the third step, we calculate the middle index once again using the formula ((0 + 1) / 2), which results in 0 when rounded down. Since the number at index 0 is negative, we move to the right by reassigning left to mid + 1. The firstPositiveIdx remains at 2.

Step 4: In the fourth and final step, the middle index is calculated using the formula ((1 + 1) / 2) which results in 1. Since the number at index 1 is positive, we reassign firstPositiveIndex to 1, and move to the left by reassigning right to mid - 1. The left pointer becomes greater than the right, which ends the loop, and we return the value at firstPositiveIdx, which is 1.

---

Part 2 - Finding the Index of the Last Negative Value

Step 1: In the first step, we are initializing two pointers, left and right, at indices 0 and 5 respectively, and the lastNegativeIdx to -1, assuming that all numbers in the array are positive until proven otherwise.

Step 2: In the second step, we calculate the middle index using the formula ((0 + 5) / 2), which results in 2 rounded down. Since the number is positive, we move to the left, by reassigning right to mid - 1.

Step 3: In the third step, we calculate the middle index once again using the formula ((0 + 1) / 2), which results in 0 when rounded down. Since the number at index 0 is negative, we reassign lastNegativeIdx to 0 and move to the right by reassigning left to mid + 1.

Step 4: In the fourth and final step, the middle index is calculated using the formula ((1 + 1) / 2) which results in 1. Since the number at index 1 is positive, we move to the left reassigning right to mid - 1. The left pointer becomes greater than the right, which ends the loop, and we return the value at lastNegativeIdx, which is 0.

With both of our searches complete, we can now use these values within our main minimumCount function that you can find below.

function minimumCount(nums) {
  const firstPositiveIdx = findFirstPositiveIndex(nums);
  const lastNegativeIdx = findLastNegativeIndex(nums);

  const negativeCount = lastNegativeIdx + 1;
  const positiveCount = nums.length - firstPositiveIdx;
  return Math.min(negativeCount, positiveCount);
}

function findFirstPositiveIndex(nums) {
  let left = 0;
  let right = nums.length - 1;
  let firstPositiveIdx = nums.length;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] <= 0) {
      left = mid + 1;
    } else {
      firstPositiveIdx = mid;
      right = mid - 1;
    }
  }
  return firstPositiveIdx;
}

function findLastNegativeIndex(nums) {
  let left = 0;
  let right = nums.length - 1;
  let lastNegativeIdx = -1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] < 0) {
      lastNegativeIdx = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return lastNegativeIdx;
}