# Maximum Count of Positive Integer and Negative Integer **Difficulty:** EASY [External](https://leetcode.com/problems/maximum-count-of-positive-integer-and-negative-integer) Canonical: https://scaleengineer.com/dsa/problems/maximum-count-of-positive-integer-and-negative-integer **Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting) **Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search) **Data structures:** Array **Companies:** [ShareChat](https://scaleengineer.com/companies/sharechat) --- ## 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**. **Follow up:** Can you solve the problem in `O(log(n))` time complexity? # Approaches ## Linear Scan This is the most straightforward approach. It involves a single pass through the array, where we explicitly count the number of positive and negative integers. We use two variables to keep track of the counts and then return the maximum of the two. **Time:** O(n), where `n` is the length of the `nums` array. This is because we must visit every element in the array once to determine its sign. · **Space:** O(1), as we only use a constant amount of extra space for the two counter variables, regardless of the input size. **Pros:** Simple to understand and implement.; It is a general solution that would also work correctly if the array were not sorted. **Cons:** Does not leverage the sorted property of the array, leading to a suboptimal time complexity.; Fails to meet the O(log n) time complexity mentioned in the problem's follow-up. ### Explanation In this approach, we initialize two integer variables, `negCount` and `posCount`, to 0. We then iterate through the `nums` array using a for-each loop. Inside the loop, for each element `num`, we check its sign. If `num` is less than 0, we increment `negCount`. If `num` is greater than 0, we increment `posCount`. We ignore any elements that are equal to 0, as per the problem description. After iterating through all the elements, the two counters will hold the total number of negative and positive integers, respectively. The final step is to return the larger of these two counts using `Math.max(posCount, negCount)`. ```java class Solution { public int maximumCount(int[] nums) { int posCount = 0; int negCount = 0; for (int num : nums) { if (num > 0) { posCount++; } else if (num < 0) { negCount++; } } return Math.max(posCount, negCount); } } ``` ### Algorithm - 1. Initialize two counters, `posCount` and `negCount`, to zero. - 2. Iterate through each element `num` in the input array `nums`. - 3. For each `num`, check if it is less than 0. If it is, increment `negCount`. - 4. Check if `num` is greater than 0. If it is, increment `posCount`. - 5. Numbers equal to 0 are skipped. - 6. After the loop completes, return the maximum value between `posCount` and `negCount`. ## Binary Search A much more efficient approach is to use binary search, which takes advantage of the fact that the input array `nums` is sorted. We can find the number of negative and positive integers by finding the boundaries where negative numbers end and positive numbers begin. This allows us to solve the problem in logarithmic time. **Time:** O(log n), where `n` is the length of the `nums` array. This is because the dominant operations are two binary searches, each of which takes logarithmic time. · **Space:** O(1), as the binary search is performed in-place and only requires a few variables to keep track of indices, using constant extra space. **Pros:** Highly efficient, with a time complexity of O(log n).; This is the optimal solution for the problem as it fully utilizes the sorted property of the input.; Satisfies the follow-up requirement. **Cons:** The implementation is more complex than a simple linear scan.; Requires careful implementation of binary search to handle edge cases correctly (e.g., arrays with all positive, all negative, or all zero elements). ### Explanation Since the array is sorted in non-decreasing order, all negative numbers will be at the beginning, followed by zeros, and then positive numbers at the end. We can use binary search to find the transition points. - **Count of Negative Numbers:** The number of negative integers is the same as the index of the first non-negative number (i.e., the first element `>= 0`). We can find this index, which represents the 'lower bound' for 0, using a binary search. Let's say this index is `firstNonNegativeIdx`. Then, `negCount = firstNonNegativeIdx`. - **Count of Positive Numbers:** The number of positive integers is the total length of the array minus the index of the first positive number (i.e., the first element `> 0`). This index is the 'upper bound' for 0. Let's say this index is `firstPositiveIdx`. Then, `posCount = nums.length - firstPositiveIdx`. We can implement two helper functions that perform binary search to find these indices. After obtaining both counts, we return their maximum. ```java class Solution { public int maximumCount(int[] nums) { // Count of negative numbers is the index of the first element >= 0. int negCount = findLowerBound(nums, 0); // Count of positive numbers is n - (index of the first element > 0). int posCount = nums.length - findUpperBound(nums, 0); return Math.max(negCount, posCount); } // Finds the index of the first element >= target (lower bound). private int findLowerBound(int[] nums, int target) { int low = 0, high = nums.length - 1; int ans = nums.length; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] >= target) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } // Finds the index of the first element > target (upper bound). private int findUpperBound(int[] nums, int target) { int low = 0, high = nums.length - 1; int ans = nums.length; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] > target) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } } ``` ### Algorithm - 1. Find the count of negative numbers. This is equivalent to finding the index of the first element that is greater than or equal to 0. This can be done using a binary search helper function. Let's call this count `negCount`. - 2. Find the count of positive numbers. This is equivalent to the total length of the array minus the index of the first element that is strictly greater than 0. This can also be found using a binary search helper function. Let's call this count `posCount`. - 3. Return the maximum of `negCount` and `posCount`. # Solutions ### Java ```java class Solution { public int maximumCount(int[] nums) { int a = 0, b = 0; for (int v : nums) { if (v > 0) { ++a; } if (v < 0) { ++b; } } return Math.max(a, b); } } ``` ### CPP ```cpp class Solution { public: int maximumCount(vector &nums) { int a = 0, b = 0; for (int &v : nums) { if (v > 0) { ++a; } if (v < 0) { ++b; } } return max(a, b); } }; ``` ### Python ```python class Solution: def maximumCount(self, nums: List[int]) -> int: a = sum(v > 0 for v in nums) b = sum(v < 0 for v in nums) return max(a, b) ```