Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Solution: Maximum Count of Positive Integer and Negative Integer

Problem Statement

Given an array nums sorted in increasing order, return the maximum between the count of positive integers and the count of negative integers.

Note: 0 is neither positive nor negative.

Examples

Example 1:

  • Input: nums = [-4, -3, -1, 0, 1, 3, 5, 7]
  • Expected Output: 4
  • Justification: The array contains three negative integers (-4, -3, -1) and four positive integers (1, 3, 5, 7). The maximum count between negatives and positives is 4.

Example 2:

  • Input: nums = [-8, -7, -5, -4, 0, 0, 0]

.....

.....

.....

Like the course? Get enrolled and start learning!
A

annejunkstuff

· 2 years ago

I was thrown off by the possibility of multiple zeros. I had to stop and think about why I should have known that I would need 2 binary searches. The answer of course is that we are targeting (as the solution states) the 'boundary between negative and positive'. And since we can have multiple zeros, the boundary between negative and zero is not always the same (or the same -/+ 1) as the boundary between zero and positive. Thus, we need two binary searches to find both possible targets.

Show 1 reply