Array
Binary Search
Counting
Description
Given an array nums
sorted in non-decreasing order, return the maximum between the number of positive integers and the number of negative integers.
In other words, if the number of positive integers in nums
is pos
and the number of negative integers is neg
, then return the maximum of pos
and neg
.
Note that 0
is neither positive nor negative.
Example 1:
Input: nums = [-2,-1,-1,1,2,3]
Output: 3
Explanation: There are 3 positive integers and 3 negative integers. The maximum count among them is 3.
Example 2:
Input: nums = [-3,-2,-1,0,0,1,2]
Output: 3
Explanation: There are 2 positive integers and 3 negative integers. The maximum count among them is 3.
Example 3:
Input: nums = [5,20,66,1314]
Output: 4
Explanation: There are 4 positive integers and 0 negative integers. The maximum count among them is 4.
Constraints:
1 <= nums.length <= 2000
-2000 <= nums[i] <= 2000
nums
is sorted in a non-decreasing order .
Follow up: Can you solve the problem in O(log(n))
time complexity?
Solutions
Solution 1: Traversal
We can directly traverse the array, count the number of positive and negative integers $a$ and $b$, and return the larger of $a$ and $b$.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
Python3 Java C++ Go TypeScript Rust C
class Solution :
def maximumCount ( self , nums : List [ int ]) -> int :
a = sum ( x > 0 for x in nums )
b = sum ( x < 0 for x in nums )
return max ( a , b )
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution {
public int maximumCount ( int [] nums ) {
int a = 0 , b = 0 ;
for ( int x : nums ) {
if ( x > 0 ) {
++ a ;
} else if ( x < 0 ) {
++ b ;
}
}
return Math . max ( a , b );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution {
public :
int maximumCount ( vector < int >& nums ) {
int a = 0 , b = 0 ;
for ( int x : nums ) {
if ( x > 0 ) {
++ a ;
} else if ( x < 0 ) {
++ b ;
}
}
return max ( a , b );
}
};
func maximumCount ( nums [] int ) int {
var a , b int
for _ , x := range nums {
if x > 0 {
a ++
} else if x < 0 {
b ++
}
}
return max ( a , b )
}
function maximumCount ( nums : number []) : number {
let [ a , b ] = [ 0 , 0 ];
for ( const x of nums ) {
if ( x > 0 ) {
++ a ;
} else if ( x < 0 ) {
++ b ;
}
}
return Math . max ( a , b );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 impl Solution {
pub fn maximum_count ( nums : Vec < i32 > ) -> i32 {
let mut a = 0 ;
let mut b = 0 ;
for x in nums {
if x > 0 {
a += 1 ;
} else if x < 0 {
b += 1 ;
}
}
std :: cmp :: max ( a , b )
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13 #define max(a, b) (a > b ? a : b)
int maximumCount ( int * nums , int numsSize ) {
int a = 0 , b = 0 ;
for ( int i = 0 ; i < numsSize ; ++ i ) {
if ( nums [ i ] > 0 ) {
++ a ;
} else if ( nums [ i ] < 0 ) {
++ b ;
}
}
return max ( a , b );
}
Solution 2: Binary Search
Since the array is sorted in non-decreasing order, we can use binary search to find the index $i$ of the first element that is greater than or equal to $1$, and the index $j$ of the first element that is greater than or equal to $0$. The number of positive integers is $a = n - i$, and the number of negative integers is $b = j$. We return the larger of $a$ and $b$.
The time complexity is $O(\log n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
Python3 Java C++ Go TypeScript Rust C
class Solution :
def maximumCount ( self , nums : List [ int ]) -> int :
a = len ( nums ) - bisect_left ( nums , 1 )
b = bisect_left ( nums , 0 )
return max ( a , b )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public int maximumCount ( int [] nums ) {
int a = nums . length - search ( nums , 1 );
int b = search ( nums , 0 );
return Math . max ( a , b );
}
private int search ( int [] nums , int x ) {
int left = 0 , right = nums . length ;
while ( left < right ) {
int mid = ( left + right ) >> 1 ;
if ( nums [ mid ] >= x ) {
right = mid ;
} else {
left = mid + 1 ;
}
}
return left ;
}
}
class Solution {
public :
int maximumCount ( vector < int >& nums ) {
int a = nums . end () - lower_bound ( nums . begin (), nums . end (), 1 );
int b = lower_bound ( nums . begin (), nums . end (), 0 ) - nums . begin ();
return max ( a , b );
}
};
func maximumCount ( nums [] int ) int {
a := len ( nums ) - sort . SearchInts ( nums , 1 )
b := sort . SearchInts ( nums , 0 )
return max ( a , b )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 function maximumCount ( nums : number []) : number {
const search = ( x : number ) : number => {
let [ left , right ] = [ 0 , nums . length ];
while ( left < right ) {
const mid = ( left + right ) >> 1 ;
if ( nums [ mid ] >= x ) {
right = mid ;
} else {
left = mid + 1 ;
}
}
return left ;
};
const i = search ( 1 );
const j = search ( 0 );
const [ a , b ] = [ nums . length - i , j ];
return Math . max ( a , b );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 impl Solution {
fn search ( nums : & Vec < i32 > , x : i32 ) -> usize {
let mut left = 0 ;
let mut right = nums . len ();
while left < right {
let mid = ( left + right ) >> 1 ;
if nums [ mid ] >= x {
right = mid ;
} else {
left = mid + 1 ;
}
}
left
}
pub fn maximum_count ( nums : Vec < i32 > ) -> i32 {
let n = nums . len ();
let i = Self :: search ( & nums , 1 );
let j = Self :: search ( & nums , 0 );
( n - i ). max ( j ) as i32
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 #define max(a, b) (a > b ? a : b)
int search ( int * nums , int numsSize , int x ) {
int left = 0 ;
int right = numsSize ;
while ( left < right ) {
int mid = ( left + right ) >> 1 ;
if ( nums [ mid ] >= x ) {
right = mid ;
} else {
left = mid + 1 ;
}
}
return left ;
}
int maximumCount ( int * nums , int numsSize ) {
int i = search ( nums , numsSize , 1 );
int j = search ( nums , numsSize , 0 );
return max ( numsSize - i , j );
}