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;
}
};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 canSame 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]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;
}Sort T: O(nlogn)
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;
}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;
}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;
}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;
}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;
}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;
}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]andcount > 0thencount += 1otherwisecount = 1.When
A[i] < A[i + 1]andcount < 0thencount -= 1otherwisecount = -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;
}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;
}
} 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;
}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.
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;
}
};Last updated
Was this helpful?