Negative numbers in sorted array
Negative numbers in sorted array
Given a sorted array of integers, find the number of negative numbers.
Expected Time Complexity: O(log n)
Examples
Array: [-5, -3, -2, 3, 4, 6, 7, 8]
Answer: 3Array: [0, 1, 2, 3, 4, 6, 7, 8]
Answer: 0Intuition
Sorted array => binary search
Find last index of number matching condition
If does not match condition - switch search space to other half
if matches condition - save, and reduce search space in current half
---
Complexity
Time - O(log N)
Space - O(1) - iterative
---
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| int getNegativeNumbersCount (int[] arr) { | |
| int lo = 0, hi = arr.length - 1; | |
| int last = -1; | |
| while (lo <= hi) { | |
| int mid = lo + (hi - lo) / 2; | |
| if (arr[mid] >= 0) { | |
| hi = mid - 1; | |
| } else { | |
| // Number is -ve, save, and search for better answer | |
| last = mid; | |
| lo = mid + 1; | |
| } | |
| } | |
| return last + 1; | |
| } | |
| } |
