easy 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]
Expected Output: 4
Justification: Here, there are four negative integers (-8, -7, -5, -4) and no positives. Thus, the maximum count is 4.

Example 3:

Input: nums = [0, 2, 2, 3, 3, 3, 4]
Expected Output: 6
Justification: This input array includes zero negative integers and six positives (2, 2, 3, 3, 3, 4). Hence, the maximum count is 6.

Constraints:

1 <= nums.length <= 2000
-2000 <= nums[i] <= 2000
nums is sorted in a non-decreasing order.

Try it yourself

Try solving this question here:

✅ 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]
Expected Output: 4
Justification: Here, there are four negative integers (-8, -7, -5, -4) and no positives. Thus, the maximum count is 4.

Example 3:

Input: nums = [0, 2, 2, 3, 3, 3, 4]
Expected Output: 6
Justification: This input array includes zero negative integers and six positives (2, 2, 3, 3, 3, 4). Hence, the maximum count is 6.

Constraints:

1 <= nums.length <= 2000
-2000 <= nums[i] <= 2000
nums is sorted in a non-decreasing order.

Solution

To solve this problem, the primary approach involves efficiently counting the positive and negative numbers in the sorted array. Given the array is already sorted, we can leverage this property by using binary search to quickly determine the boundary between negative and positive integers, optimizing the count operation. This boundary identification will allow for rapid determination of the counts of negative and positive integers without having to iterate through every element, thus promising a time-efficient solution.

The sorted nature of the array ensures that once we find the first positive integer, all subsequent integers are positive, allowing this method to be particularly effective.

Step-by-step Algorithm

Initialization:
- Declare and initialize start to 0 and end to nums.length - 1.
- Initialize maxNegatives and maxPositives to 0 to store the maximum counts of negative and positive numbers respectively.
First Pass: Counting Negative Numbers:
- While start is less than or equal to end:
  - Compute the midpoint mid = start + (end - start) / 2.
  - If nums[mid] < 0, it indicates that we still have negative numbers:
    - Update maxNegatives to mid + 1 since this counts how many elements are negative (indices from 0 to mid).
    - Set start to mid + 1 to continue searching to the right of mid.
  - Else, adjust end to mid - 1 to search in the left half for more negatives.
Second Pass: Counting Positive Numbers:
- Reset start to 0 and end to nums.length - 1.
- While start is less than or equal to end:
  - Compute the midpoint mid = start + (end - start) / 2.
  - If nums[mid] > 0, it indicates that we are in the range of positive numbers:
    - Update maxPositives to nums.length - mid to count all positive numbers from mid to the end of the array.
    - Set end to mid - 1 to continue searching to the left of mid for the start of positive numbers.
  - Else, adjust start to mid + 1 to search in the right half for the first positive number.
Return the Maximum Count:
- Use the Math.max function to determine and return the maximum of maxNegatives and maxPositives.

Algorithm Walkthrough

Let's consider the input: nums = [-4, -3, -1, 0, 1, 3, 5, 7].

Counting Negative Numbers:
- Start with start = 0, end = 7.
- Iteration 1: mid = 3, value at mid is 0. Adjust end to 2.
- Iteration 2: mid = 1, value at mid is -3. It is negative, so update maxNegatives to 2 and move start to 2.
- Iteration 3: mid = 2, value at mid is -1. It is negative, so update maxNegatives to 3 and move start to 3.
- No more elements to the left; loop exits with maxNegatives = 3.
Counting Positive Numbers:
- Reset with start = 0, end = 7.
- Iteration 1: mid = 3, value at mid is 0. Adjust start to 4.
- Iteration 2: mid = 5, value at mid is 3. It is positive, so update maxPositives to 3 and move end to 4.
- Iteration 3: mid = 4, value at mid is 1. It is positive, so update maxPositives to 4 and move end to 3.
- No more elements to the right; loop exits with maxPositives = 4.
Maximum Count:
- maxNegatives = 3 and maxPositives = 4.
- Final result is Math.max(3, 4) which yields 4.

Code

java

import java.util.Arrays;

class Solution {

  public int maximumCount(int[] nums) {
    int start = 0,
      end = nums.length - 1;
    int maxNegatives = 0,
      maxPositives = 0; // To hold the counts of negatives and positives

    // First pass to find the count of negative numbers
    while (start <= end) {
      int mid = start + (end - start) / 2;
      if (nums[mid] < 0) {
        maxNegatives = mid + 1; // Update count of negatives
        start = mid + 1; // Move to the right
      } else {
        end = mid - 1; // Continue searching in the left half
      }
    }

    start = 0;
    end = nums.length - 1;

    // Second pass to find the count of positive numbers
    while (start <= end) {
      int mid = start + (end - start) / 2;
      if (nums[mid] > 0) {
        maxPositives = nums.length - mid; // Update count of positives
        end = mid - 1; // Continue searching in the left half
      } else {
        start = mid + 1; // Move to the right
      }
    }

    // Return the maximum of the counts of negatives and positives
    return Math.max(maxNegatives, maxPositives);
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] nums1 = { -4, -3, -1, 0, 1, 3, 5, 7 };
    System.out.println("Example 1: " + solution.maximumCount(nums1)); // Expected Output: 4

    // Example 2
    int[] nums2 = { -8, -7, -5, -4, 0, 0, 0 };
    System.out.println("Example 2: " + solution.maximumCount(nums2)); // Expected Output: 4

    // Example 3
    int[] nums3 = { 0, 2, 2, 3, 3, 3, 4 };
    System.out.println("Example 3: " + solution.maximumCount(nums3)); // Expected Output: 6
  }
}

Complexity Analysis

Time Complexity

The solution involves two separate binary searches over the input array:

First Binary Search: This search identifies the count of negative numbers. It performs in time, where (n) is the number of elements in the array.
Second Binary Search: This search counts the positive numbers. It also runs in time.

Since each binary search runs independently but sequentially, the total time complexity remains .

Space Complexity

The solution uses a constant amount of extra space for variables such as start, end, mid, maxNegatives, and maxPositives, regardless of the input size. Therefore, the space complexity is .

🤖 Don't fully get this? Learn it with Claude

Stuck on Maximum Count of Positive Integer and Negative Integer? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Maximum Count of Positive Integer and Negative Integer** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Maximum Count of Positive Integer and Negative Integer** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Maximum Count of Positive Integer and Negative Integer**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Maximum Count of Positive Integer and Negative Integer**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Introduction to Searching Algorith Minimum Common Value →