# 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](https://leetcode.com/problems/maximum-difference-between-increasing-elements/)

```cpp
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](https://leetcode.com/problems/majority-element/)

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

* 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.

```python
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](https://leetcode.com/problems/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.

```python
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](https://leetcode.com/problems/longest-mountain-in-array/)

Count increments and decrements. Reset when encounter flat.

```java
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](https://leetcode.com/problems/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)*

```java
    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](https://leetcode.com/problems/find-the-duplicate-number/)

Same as [Find LinkedList cycle](/decode-leetcode/linkedlist.md#142-linked-list-cycle-ii). Use fast and slow pointer to move in the same array. Reset slow and return when they meet again.

```java
    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](https://leetcode.com/problems/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.&#x20;

```java
    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](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/)

```java
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](https://leetcode.com/problems/can-place-flowers/)

```java
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](https://leetcode.com/problems/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.&#x20;

```java
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](https://leetcode.com/problems/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]`.&#x20;

* When `A[i] > A[i + 1]` and `count > 0` then `count += 1` otherwise `count = 1`. &#x20;
* When `A[i] < A[i + 1]` and `count < 0` then `count -= 1` otherwise `count = -1`. &#x20;

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

```java
   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](https://leetcode.com/problems/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.

```java
    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](https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/)

```java
    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](https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/) ([846. Hand of Straights](https://leetcode.com/problems/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

```java
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;
}
```

&#x20;   2\. Sort + map

```java
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](https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/)

```cpp
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](https://leetcode.com/problems/maximum-frequency-after-subarray-operation/)

```cpp
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](https://leetcode.com/problems/check-if-array-is-sorted-and-rotated/)

```cpp
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](https://leetcode.com/problems/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:

  ```cpp
  min(minPos, maxPos) - left
  ```

```cpp
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](https://leetcode.com/problems/divide-array-into-arrays-with-max-difference/)

sort and detect

```cpp
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](https://leetcode.com/problems/longest-harmonious-subsequence/)

```cpp
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](https://leetcode.com/problems/find-lucky-integer-in-an-array/)

```cpp
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](https://leetcode.com/problems/split-the-array/)

```cpp
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;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://howardyangemail.gitbook.io/decode-leetcode/array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.