Given an array nums sorted in non-decreasing order, return the maximum between the number of positive integers and the number of negative integers.
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] <= 2000nums is sorted in a non-decreasing order.
Follow up: Can you solve the problem in O(log(n)) time complexity?
This approach involves a simple linear scan through the array to count the number of negative and positive integers. As the array is sorted, all negative numbers will appear before non-negative numbers and all positive numbers after non-positive numbers.
This C code defines a function maximumCount which iterates through the given array nums, counts the positive and negative integers, and returns the maximum count of either positive or negative integers. Note that zero is ignored during counting.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1) as only a few additional variables are used.
Use binary search to find the first non-negative and the first positive number. Given the sorted property, this allows us to find the boundaries efficiently. The number of negative integers is equivalent to the index of the first non-negative integer, while the number of positive integers is the total length minus the index of the first positive integer.
This C code uses two binary search functions to find the index of the first non-negative and first positive numbers. By calculating the numbers of positives and negatives based on these indices, the maximum can be found in log time.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n).
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Linear Scan | Time Complexity: O(n), where n is the length of the array. |
| Approach 2: Binary Search | Time Complexity: O(log n). |
Maximum Count of Positive Integer and Negative Integer | Leetcode 2529 | codestorywithMIK • codestorywithMIK • 4,223 views views
Watch 9 more video solutions →Practice Maximum Count of Positive Integer and Negative Integer with our built-in code editor and test cases.
Practice on FleetCode