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
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]
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;
}
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] 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;
}
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;
}
Same as . Use fast and slow pointer to move in the same array. Reset slow and return when they meet again.