int kthMissing(vector<int> &arr, int k) {
// Your code goes here
int low = 0;
int high = arr.size()-1;
int ans = arr.size() + k;
while(low <= high) {
int mid = low + (high-low) / 2;
if(arr[mid] > mid+k) {
high = mid - 1;
ans = mid + k;
} else {
low = mid+1;
}
}
return ans;
}Category: Coding Prep
GFG PTOD | 18 Dec | Allocate Minimum Pages
bool isPossible(int k, int mid, const vector<int> &arr) {
int students = 1, curPage = 0;
for(pages : arr) {
if(pages > mid) return false;
if(curPage + pages > mid) {
students++;
curPage = pages;
if(students > k) return false;
} else {
curPage += pages;
}
}
return true;
}
int findPages(vector<int> &arr, int k) {
// code here
if(k > arr.size()) return -1;
int ret = -1;
int low = *max_element(arr.begin(), arr.end()); // max value in array
int high = accumulate(arr.begin(), arr.end(), 0); // sum of all elements in array
while(low <= high) {
int mid = low + (high-low) /2;
if(isPossible(k, mid, arr)) {
ret = mid;
high = mid-1;
} else {
low = mid+1;
}
}
return ret;
}GFG PTOD | 17th Dec | Aggressive Cows
bool isPossible(int mid, int k, vector<int> &stalls) {
int count = 1;
int lastPos = stalls[0];
for(int i=1; i < stalls.size(); i++) {
if(stalls[i] - lastPos >= mid) {
count++;
lastPos = stalls[i];
if(count == k) {
return true;
}
}
}
return false;
}
int aggressiveCows(vector<int> &stalls, int k) {
// Write your code here
sort(stalls.begin(), stalls.end());
int low = 1;
int high = stalls.back() - stalls.front();
int res = 0;
while(low <= high) {
int mid = low + (high - low) / 2;
if(isPossible(mid, k, stalls)) {
res = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return res;
}45. Jump Game II (Medium)
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where: 0 <= j <= nums[i] and i + j < n Return the minimum number of jumps to reach nums[n -…
55. Jump Game (Medium)
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise. Example 1: Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3…
189. Rotate Array (Medium)
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. Example 1: Example 2: Solutions 1 : Solutions 2 : Solution 3:
169. Majority Element (Easy)
Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Example 1: Input: nums = [3,2,3] Output: 3 Example 2: Input: nums = [2,2,1,1,1,2,2] Output: 2 Solution 1 Solution 2
189. Rotate Array (medium)
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. Example 1: Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4] Example 2: Input: nums = [-1,-100,3,99], k = 2…
26. Remove Duplicates from Sorted Array (easy)
https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150 Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums. Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things: Change the array nums such that the first k elements…
Read More “26. Remove Duplicates from Sorted Array (easy)” »
27. Remove Element (easy)
https://leetcode.com/problems/remove-element/?envType=study-plan-v2&envId=top-interview-150 Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val. Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things: Change the array nums such that the first k elements…