Positive or Negative

See the original problem on HackerRank.

Solutions

The linear solution is simple: just count the frequencies of both negative and positive integers.

However, the optimal solution is more interesting: leveraging the sorted nature of the array, we can exploit binary search. Here’s where a crucial detail comes into play: 0 is neither positive nor negative. Consequently, searching for 0 presents us with an opportunity to swiftly determine the count of positive and negative integers.

In essence, we need to recall two fundamental concepts regarding binary searches:

• Lower bound: locates a specified element or the next one if the specified element is absent;
• Upper bound: locates the next element after the specified one.

Clearly, both are binary searches, operating in logarithmic time.

The idea here is to find both lower bound and upper bound of 0:

• all the elements before the lower bound of 0 are necessarily negative (lower bound of 0 finds either 0 or the first positive);
• all the elements after the upper bound of 0 are necessarily positive (upper bound of 0 finds the first positive).

For example:

1
2

0  1  2  3 4 5
-4 -2 -1 0 5 7

• lower bound(0)=3, indeed the number of negative integers is 3-0=3
• upper bound(0)=4, indeed the number of positive integers is 5-4=1

Another example without 0:

1
2

0  1  2  3 4
-4 -2 -1 5 7

• lower bound(0)=3, indeed the number of negative integers is still 3-0=3
• upper bound(0)=4, indeed the number of positive integers is still 4-3=1

Another example with more 0:

1
2

0  1  2 3 4 5 6 7 8 9
-1 -1 0 0 0 5 7 8 9 10

• lower bound(0)=2, indeed the number of negative integers is 2-0=2
• upper bound(0)=5, indeed the number of positive integers is 10-5=5

The most concise C++ code is here below:

1
2

auto [b,e] = equal_range(begin(nums), end(nums), 0);
return max(distance(begin(nums), b), distance(e, end(nums)));

equal_range combines both lower_bound and upper_bound into a single function call.

In Python, for example, we explicitly call both:

1
2
3

neg = bisect_left(nums, 0)
pos = len(nums) - bisect_right(nums, 0)
return max(neg, pos)