Table of contents

• Given problem
• Using brute-force algorithm
• Using Binary Search algorithm
• Wrapping up

Given problem

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.

Using brute-force algorithm

class Solution {
    public int maximumCount(int[] nums) {
        int lastIdxNeg = -1;
        int firstIdxPos = nums.length;

        // find the last index of the negative element
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] < 0) {
                lastIdxNeg++;
            }
        }

        System.out.println("last idex of negative element: " + lastIdxNeg);

        // find the first index of the positive element
        for (int i = nums.length - 1; i >= 0; --i) {
            if (nums[i] > 0) {
                firstIdxPos--;
            }
        }

        System.out.println("first idex of positive element: " + firstIdxPos);
        return Math.max(lastIdxNeg + 1, nums.length - firstIdxPos);
    }
}

The complexity of this solution:

• Time complexity: O(n).
• Space complexity: O(1).

Using Binary Search algorithm

Below is our source code that use Binary Search algorithm:

class Solution {
    public int maximumCount(int[] nums) {
        int lowerPoint = lowerBound(nums, 0);
        int upperPoint = upperBound(nums, 0);

        if (lowerPoint == -1 && upperPoint == -1) {
            return 0;
        }

        if (lowerPoint == -1) lowerPoint = 0;
        if (upperPoint == -1) upperPoint = 0;

        return Math.max(upperPoint + 1, nums.length - lowerPoint);
    }

    /**
     * Find the first element that is greater than 0.
     */
    private static int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }

        if (nums[left] > target) {
            return left;
        }

        if (right < nums.length && nums[right] > target) {
            return right;
        }

        return -1;
    }

    /**
     * Find the last element that is less than 0.
     */
    private static int upperBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }

        if (right < nums.length && nums[right] < target) {
            return right;
        }

        if (nums[left] < target) {
            return left;
        }

        return -1;
    }

}

The complexity of this solution is:

• Time complexity: O(logn).
• Space complexity: O(1).

Wrapping up

Refer:

2529. Maximum Count of Positive Integer and Negative Integer