main.go

// Source: https://leetcode.com/problems/maximum-count-of-positive-integer-and-negative-integer
// Title: Maximum Count of Positive Integer and Negative Integer
// Difficulty: Easy
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 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?
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

package main

import (
	"slices"
)

// Linear
func maximumCount(nums []int) int {
	pos, neg := 0, 0
	for _, num := range nums {
		if num > 0 {
			pos++
		} else if num < 0 {
			neg++
		}
	}
	return max(pos, neg)
}

// Binary Search
func maximumCount2(nums []int) int {
	n := len(nums)
	idx1, _ := slices.BinarySearch(nums, 0)                                              // bisect left
	idx2, _ := slices.BinarySearchFunc(nums, 0, func(e, t int) int { return e - t - 1 }) // bisect right
	return max(idx1, n-idx2)
}