2529: Maximum-Count-of-Positive-Integer-and-Negative-Integer
Easy

table of contents

I mean, the O(n) solution is quite obvious; just iterate through nums and return the maximum number out of the number of negative numbers and positive numbers.

The O(log(n)) solution is also quite obvious, as you can simply just run 2 binary search algorithms to find the index position of the last negative number and index position of the first positive number. Then, using simple arithmetic, you can retrieve the number of negative and positive numbers (as nums is sorted in non-decreasing order) and simply return the larger one.

code

class Solution {
public:
    int maximumCount(vector<int>& nums) {
        int left = 0;
        int right = nums.size()-1;
        int neg = 0;
        while (left <= right) {
            int mid = left - (left - right)/2;
            if (nums[mid] <= -1) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }
        neg = left;

        right = nums.size()-1;
        while (left <= right) {
            int mid = left - (left - right)/2;
            if (nums[mid] <= 0) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }

        int pos = left;

        return max(neg, (int)nums.size()-pos);
    }
};

complexity