Negative numbers in sorted array Editorial

Practice Problem Link: Negative numbers in sorted array | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a sorted number of array of integers, find the number of negative numbers.

Naive Approach

A simple solution is to just iterate the array and keep the count of the numbers that are negative.

Analysis

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

Implementation

C++

int getNegativeNumbersCount(vector<int> &arr) {
   int countNegative = 0;
   for (int i = 0; i < arr.size(); i++) {
       if (arr[i] < 0) {
           countNegative++;
       }
   }
   return countNegative;
}

Java

class Solution {
   int getNegativeNumbersCount (int[] arr) {
       int countNegative = 0;
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] < 0) {
               countNegative++;
           }
       }
       return countNegative;
   }
}

Optimal Approach

The problem can be solved by using the binary search method. Since the array is sorted there will be only one point in the array where the two consecutive elements are negative and positive. All we need to do is find that particular index.

• Initialize three variables, low = 0, high = n - 1 and mid.
• Perform a binary search while (high >= low) and assign mid = (high + low ) /  2;
• If arr[mid] is negative and arr[mid + 1] is positive then return (index + 1) as ans.
• If both arr[mid] and arr[mid + 1] are positive then the index which has the last negative element must be in the first half otherwise the index must be in the second half.

Analysis

• Time Complexity: O(log(n))
• Space Complexity: O(1)

Implementation

C++

int binarySearch (vector<int> arr, int low, int high) {
   if (high > low) {
       int mid = (high + low) / 2;
       if (arr[mid] < 0 && arr[mid + 1] >= 0) {
           return mid;
       } else if (arr[mid] >= 0 && arr[mid + 1] >= 0) {
           return binarySearch(arr, 0, mid);
       } else {
           return binarySearch(arr, mid + 1, high);
       }
   }
   return -1;
}
int getNegativeNumbersCount(vector<int> &arr) {
   if (arr[0] >= 0) {
		return 0;
	}
   if (arr[arr.size()-1] < 0) {
		return arr.size();
	}
   return binarySearch (arr, 0, arr.size() - 1) + 1; //index + 1
}

Java

class Solution {
   int binarySearch (int[] arr, int low, int high) {
       if (high > low) {
           int mid = (high + low) / 2;
           if (arr[mid] < 0 && arr[mid + 1] >= 0) {
               return mid;
           } else if (arr[mid] >= 0 && arr[mid + 1] >= 0) {
               return binarySearch(arr, 0, mid);
           } else {
               return binarySearch(arr, mid + 1, high);
           }
       }
       return -1;
   }
   int getNegativeNumbersCount (int[] arr) {
       if(arr[0] >= 0) {
		   return 0;
	   }
	   if(arr[arr.length-1] < 0) {
		   return arr.length;
	   }
       return binarySearch(arr, 0, arr.length) + 1; // index + 1
   }
}