Array

66. Plus One

881. Boats to Save People

448. Find All Numbers Disappeared in an Array

280. Wiggle Sort

2016. Maximum Difference Between Increasing Elements

class Solution {
public:
    int maximumDifference(vector<int>& nums) {
        int minVal = std::numeric_limits<int>::max();
        int maxDiff = -1;
        for (int n : nums) {
            if (n <= minVal) {
                minVal = n;
            } else {
                maxDiff = std::max(maxDiff, n - minVal);
            }
        }
        return maxDiff;
    }
};

169. Majority Element

Boyer-Moore Voting Algorithm. Calculate the candidate and it is vote (count).

• vote + 1: when the candidate == current number

• vote - 1: when the candidate != current number

If the vote is reduced to 0, reset candidate to the current number.

def majorityElement(self, nums: List[int]) -> int:
    vote = 0
    can = None
    for i in range(0, len(nums)):
        if vote == 0:
            can = nums[i]
        if can == nums[i]:
            vote += 1
        else:
            vote -= 1
    return can

229. Majority Element II

Same as 169, instead of using one candidate, use two candidates and maintain their count. Output the candidate which has more than length / 3 votes.

def majorityElement(self, nums: List[int]) -> List[int]:
    if not nums:
        return []
    can1, can2, vote1, vote2 = 0,1,0,0
    for n in nums:
        if can1 == n:
            vote1 += 1
        elif can2 == n:
            vote2 += 1
        elif vote1 == 0:
            can1, vote1 = n, 1
        elif vote2 == 0:
            can2, vote2 = n, 1
        else:
            vote1, vote2 = vote1 - 1, vote2 - 1
    return [n for n in (can1, can2) if nums.count(n) > len(nums) // 3]

845. Longest Mountain in Array

Count increments and decrements. Reset when encounter flat.

public int longestMountain(int[] A) {
    int inc = 0, dec = 0, res = 0;
    int savedinc = 0;
    for (int i = 0; i < A.length; i++) {
        if (i > 0 && A[i - 1] < A[i]) {
            dec = 0;
            inc++;
        } else if (i > 0 && A[i - 1] > A[i]) {
            if (inc != 0) {
                savedinc = inc;
                inc = 0;
            }
            dec++;
        } else {
            savedinc = 0;
            inc = 0;
            dec = 0;
            continue;
        }
        if (savedinc != 0 && dec != 0) {
            res = Math.max(res, savedinc + dec + 1);
        }
    }
    return res;
}

128. Longest Consecutive Sequence

1. Sort T: O(nlogn)

2. Intelligent Sequence Building:

   Add all numbers to a set. Loop over all numbers, search if the current number is a start of the sequence. if (!set.contains(n - 1)) If yes, keep search and build the sequence. T: O(n)

    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) set.add(n);
        int maxLen = 0;
        for (int n : nums) {
            if (!set.contains(n - 1)) {
                int i = n;
                int localSeq = 0;
                while (set.contains(i)) {
                    i++;
                    localSeq++;
                    maxLen = Math.max(maxLen, localSeq);
                }
            }
        }
        return maxLen;
    }

287. Find the Duplicate Number

Same as Find LinkedList cycle. Use fast and slow pointer to move in the same array. Reset slow and return when they meet again.

    public int findDuplicate(int[] nums) {
        int fast = 0, slow = 0;
        while (true) {
            fast = nums[nums[fast]];
            slow = nums[slow];
            if (fast == slow) break;
        }
        slow = 0;
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return fast;
    }

442. Find All Duplicates in an Array

Since the array elements in range 1 ≤ a[i] ≤ n (n = size of array). Each element has corresponding pos may be once or twice. We mark the number at visited position negative, if we encounter this negative element twice, then this is a result.

    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int pos = Math.abs(nums[i]) - 1;
            if (nums[pos] < 0) res.add(nums[i]);
            nums[pos] = -nums[pos];
        }
        return res;
    }

448. Find All Numbers Disappeared in an Array

public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> res = new ArrayList<>();
    if (nums == null || nums.length == 0) return res;
    for (int i = 0; i < nums.length; i++) {
        int val = Math.abs(nums[i]) - 1;
        if (nums[val] > 0) nums[val] = -nums[val];
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) res.add(i + 1);
    }
    return res;
}

605. Can Place Flowers

public boolean canPlaceFlowers(int[] flowerbed, int k) {
    if (k == 0) return true;
    int n = flowerbed.length;
    for (int i = 0; i < flowerbed.length; i++) {
        if ((i == 0 || (i > 0 && flowerbed[i - 1] == 0)) && flowerbed[i] == 0 && (i == n - 1 || (i < n && flowerbed[i + 1] == 0))) {
            flowerbed[i] = 1;
            k--;
            if (k == 0) return true;
        }
    }    
    return k == 0;
}

41. First Missing Positive

Once all numbers are made positive, if any number is found in range [1,N] then attach -ve sign to the corresponding index. So for 1, 0th element becomes -ve, for 2 it is 1st considering 0 based index.

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    
    // 1. mark numbers (num < 0) and (num > n) with a special marker number (n+1) 
    // (we can ignore those because if all number are > n then we'll simply return 1)
    for (int i = 0; i < n; i++) {
        if (nums[i] <= 0 || nums[i] > n) {
            nums[i] = n + 1;
        }
    }
    // note: all number in the array are now positive, and on the range 1..n+1
    
    // 2. mark each cell appearing in the array, by converting the index for that number to negative
    for (int i = 0; i < n; i++) {
        int num = Math.abs(nums[i]);
        if (num > n) {
            continue;
        }
        num--; // -1 for zero index based array (so the number 1 will be at pos 0)
        if (nums[num] > 0) { // prevents double negative operations
            nums[num] = -1 * nums[num];
        }
    }
    
    // 3. find the first cell which isn't negative (doesn't appear in the array)
    for (int i = 0; i < n; i++) {
        if (nums[i] >= 0) {
            return i + 1;
        }
    }
    
    // 4. no positive numbers were found, which means the array contains all numbers 1..n
    return n + 1;
}

978. Longest Turbulent Subarray

Use a count to determine the length of the turbulent subarray. Flip count every loop by using count *= -1. Detect if the pattern match the current array or start a new one. Otherwise reset count to 0. For example, [4,2,10,7,8].

• When A[i] > A[i + 1] and count > 0 then count += 1 otherwise count = 1.

• When A[i] < A[i + 1] and count < 0 then count -= 1 otherwise count = -1.

Maintain the max result by update the absolute value of count.

   public int maxTurbulenceSize(int[] A) {
        int res = 0, count = 0;
        for (int i = 0; i < A.length - 1; i++) {
            if (A[i] > A[i + 1]) {
                count = count > 0 ? count + 1 : 1;
            } else if (A[i] < A[i + 1]) {
                count = count < 0 ? count - 1 : -1;
            } else {
                count = 0;
            }
            res = Math.max(res, Math.abs(count));
            count *= -1;
        }
        return res + 1;
    }

1152. Analyze User Website Visit Pattern

Use HashMap to store a list of timestamp-website pairs for each user. Sort the list, create pattern for each combination. Use a hashset to remove duplicate and a frequency hashmap to find the most frequent pattern.

    public List<String> mostVisitedPattern(String[] username,
                                           int[] timestamp,
                                           String[] website) {
        Map<String, List<Pair>> map = new HashMap<>();
        for (int i = 0; i < username.length; i++) {
            map.putIfAbsent(username[i], new ArrayList<>());
            map.get(username[i]).add(new Pair(timestamp[i], website[i]));
        }
        Map<String, Integer> freq = new HashMap<>();
        String res = null;
        for (String user : map.keySet()) {
            List<Pair> list = map.get(user);
            list.sort(new Comparator<Pair>() {
                @Override
                public int compare(Pair o1, Pair o2) {
                    return o1.timestamp - o2.timestamp;
                }
            });
            Set<String> set = new HashSet<>();
            for (int i = 0; i < list.size() - 2; i++) {
                for (int j = i + 1; j < list.size() - 1; j++) {
                    for (int k = j + 1; k < list.size(); k++) {
                        String pattern = list.get(i).website + "," + list.get(j).website + "," + list.get(k).website;
                        if (!set.contains(pattern)) {
                            set.add(pattern);
                            freq.put(pattern, freq.getOrDefault(pattern, 0) + 1);
                        }
                        if (res == null 
                            || freq.get(pattern) > freq.get(res) 
                            || (freq.get(pattern) == freq.get(res)) && pattern.compareTo(res) < 0) {
                            res = pattern;
                        }
                    }
                }
            }
        }
        return res == null ? new ArrayList<>() : Arrays.asList(res.split(","));
    }

    class Pair {
        int timestamp;
        String website;
        Pair(int t, String w) {
            this.website = w;
            this.timestamp = t;
        }
    }

1031. Maximum Sum of Two Non-Overlapping Subarrays

    public int maxSumTwoNoOverlap(int[] A, int L, int M) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int n = A.length;
        int[] preSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = A[i] + preSum[i];
        }
        int lMax = preSum[L], mMax = preSum[M];
        int res = preSum[L + M];
        for (int i = L + M; i <= n; i++) {
            //case 1: L subarray is always before M subarray
            lMax = Math.max(lMax, preSum[i - M] - preSum[i - M - L]);
            //case 2: M subarray is always before L subarray
            mMax = Math.max(mMax, preSum[i - L] - preSum[i - M - L]);
            //compare two cases and update res
            res = Math.max(res, Math.max(lMax + preSum[i] - preSum[i - M], mMax + preSum[i] - preSum[i - L]));
        }
        return res;
    }

1296. Divide Array in Sets of K Consecutive Numbers (846. Hand of Straights)

Find a starting number and check if there is any numbers which can make a straight from the numbers. The starting point is the smallest number exists.

1. PriorityQueue

public boolean isPossibleDivide(int[] nums, int k) {
    int n = nums.length;
    if (n % k != 0) return false;
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int num : nums) pq.offer(num);
    while (!pq.isEmpty()) {
        int start = pq.poll();
        for (int i = 1; i < k; i++) {
            if (!pq.isEmpty() && !pq.remove(start + i)) {
                return false;
            }
        }
    }
    return true;
}

2. Sort + map

public boolean isPossibleDivide(int[] nums, int k) {
    int n = nums.length;
    if (n % k != 0) return false;
    Arrays.sort(nums);
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    for (int i = 0; i < n; i++) {
        if (map.get(nums[i]) == 0) {
            continue;
        }
        for (int inc = 0; inc < k; inc++) {
            if (map.get(nums[i] + inc) == null || map.get(nums[i] + inc) <= 0) {
                return false;
            }
            map.put(nums[i] + inc, map.get(nums[i] + inc) - 1);
        }
    }
    return true;
}

1296. Divide Array in Sets of K Consecutive Numbers

class Solution {
public:
    bool isPossibleDivide(vector<int>& nums, int k) {
        int n = nums.size();
        if (n % k != 0) return false;

        std::map<int, int> countMap;
        for (int num : nums) {
            countMap[num]++;
        }

        for (auto it = countMap.begin(); it != countMap.end(); ++it) {
            int key = it->first;
            int freq = it->second;
            if (freq == 0) continue;

            for (int i = 0; i < k; ++i) {
                int cur = key + i;
                if (countMap[cur] < freq) return false;
                countMap[cur] -= freq;
            }
        }

        return true;
    }
};

3434. Maximum Frequency After Subarray Operation

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        constexpr int MAX_VAL = 50;
        unordered_map<int,int> freq;
        int baseCount = 0, maxExtra = 0;

        // Count how many `k` are already in nums
        for (int x : nums) if (x == k) baseCount++;

        // Apply Kadane for each possible target value
        for (int t = 1; t <= MAX_VAL; ++t) {
            if (t == k) continue;
            int cur = 0, best = 0;
            for (int x : nums) {
                if (x == t) cur++;
                else if (x == k) cur--;
                
                if (cur < 0) cur = 0;
                best = max(best, cur);
            }
            maxExtra = max(maxExtra, best);
        }

        return baseCount + maxExtra;
    }
};

1752. Check if Array Is Sorted and Rotated

class Solution {
public:
    bool check(vector<int>& nums) {
        int rotationPoint = 0, n = nums.size();
        for (int i = 1; i < n; ++i) {
            if (nums[i] < nums[i - 1]) {
                rotationPoint = i;
                break;
            }
        }
        for (int i = rotationPoint + 1; i < n; ++i) {
            if (nums[i] < nums[i - 1]) return false;
        }
        if (rotationPoint > 0 && nums[n - 1] > nums[0]) return false;
        return true;
    }
};

2444. Count Subarrays With Fixed Bounds

• set max/min position and update dynamically

• use left index to bound the left range which within the min/max

• add to result, make sure no -ve values:

  min(minPos, maxPos) - left

public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        int minPos = -1, maxPos = -1;
        int left = -1, res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] < minK || nums[i] > maxK) {
                left = i;
            }
            if (nums[i] == minK) minPos = i;
            if (nums[i] == maxK) maxPos = i;
            res += max(min(minPos, maxPos) - left, 0);
        }
        return res;
    }
};

2966. Divide Array Into Arrays With Max Difference

sort and detect

class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for (int i = 0; i < nums.size(); i += 3) {
            if (nums[i + 2] - nums[i] > k) return {};
            res.push_back({nums[i], nums[i + 1], nums[i + 2]});
        }
        return res;
    }
};

594. Longest Harmonious Subsequence

class Solution {
public:
    // sort + sliding window
    int findLHS(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int L = 0, R = 0, res = 0;
        while (R < nums.size()) {
            while (nums[R] - nums[L] > 1) {
                L++;
            }
            if (nums[R] - nums[L] == 1) {
                res = max(res, R - L + 1);
            }
            R++;
        }
        return res;
    }
    
    // hashmap
    int findLHS(vector<int>& nums) {
        map<int, int> map;
        for (int n : nums) {
            map[n]++;
        }
        int res = 0;
        for (const auto& [k, v] : map) {
            if (map.count(k + 1)) {
                res = max(res, v + map[k + 1]);
            }
        }
        return res;
    }

    // hashmap
    int findLHS(vector<int>& nums) {
        map<int, int> map;
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            map[nums[i]]++;
            if (map.count(nums[i] + 1)) {
                res = max(res, map[nums[i] + 1] + map[nums[i]]);
            }
            if (map.count(nums[i] - 1)) {
                res = max(res, map[nums[i] - 1] + map[nums[i]]);
            }
        }
        return res;
    }
};

1394. Find Lucky Integer in an Array

class Solution {
public:
    int findLucky(vector<int>& arr) {
        map<int, int> map;
        for (int n : arr) map[n]++;
        int res = -1;
        for (const auto& [k , v] : map) {
            if (k == v) {
                res = max(res, v);
            }
        }
        return res;
    }
};

3046. Split the Array

class Solution {
public:
    bool isPossibleToSplit(vector<int>& nums) {
        map<int, int> map;
        for (int n : nums) map[n]++;
        int odd = 0;
        for (const auto& [k, v] : map) {
            if (v > 2) return false;
            if (v == 1) odd++;
        }
        return odd % 2 == 0;
    }
};