Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2529.html
2529. Maximum Count of Positive Integer and Negative Integer
Description
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
ispos
and the number of negative integers isneg
, then return the maximum ofpos
andneg
.
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?
Solutions
-
class Solution { public int maximumCount(int[] nums) { int a = nums.length - search(nums, 1); int b = search(nums, 0); return Math.max(a, b); } private int search(int[] nums, int x) { int left = 0, right = nums.length; while (left < right) { int mid = (left + right) >> 1; if (nums[mid] >= x) { right = mid; } else { left = mid + 1; } } return left; } }
-
class Solution { public: int maximumCount(vector<int>& nums) { int a = nums.end() - lower_bound(nums.begin(), nums.end(), 1); int b = lower_bound(nums.begin(), nums.end(), 0) - nums.begin(); return max(a, b); } };
-
class Solution: def maximumCount(self, nums: List[int]) -> int: a = len(nums) - bisect_left(nums, 1) b = bisect_left(nums, 0) return max(a, b)
-
func maximumCount(nums []int) int { a := len(nums) - sort.SearchInts(nums, 1) b := sort.SearchInts(nums, 0) return max(a, b) } func max(a, b int) int { if a > b { return a } return b }
-
function maximumCount(nums: number[]): number { const search = (target: number) => { let left = 0; let right = n; while (left < right) { const mid = (left + right) >>> 1; if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } return left; }; const n = nums.length; const i = search(0); const j = search(1); return Math.max(i, n - j); }
-
impl Solution { fn search(nums: &Vec<i32>, target: i32) -> usize { let mut left = 0; let mut right = nums.len(); while left < right { let mid = (left + right) >> 1; if nums[mid] < target { left = mid + 1; } else { right = mid; } } left } pub fn maximum_count(nums: Vec<i32>) -> i32 { let n = nums.len(); let i = Self::search(&nums, 0); let j = Self::search(&nums, 1); i.max(n - j) as i32 } }