Code template for coding interview
- Binary search
- lower_bound
- pseudocode
- Python3
- Java
- C++
- upper_bound
- pseudocode
- Python3
- Java
- C++
- lower_bound
- Sliding window
- Monotonic stack
- Prefix tree
- BFS
- DFS
- Rolling hash
- Topological sort
- Union Find
Return the index of first valid element in nums
BINARY_SEARCH(nums, target)
// loop invariant: first valid element ∈ [left, right)
left, right = 0, nums.length
while left < right
mid = left + (right - left) // 2
if VALID(nums[mid], target)
right = mid
else
left = mid + 1
return left
Return the index of first element greater or equal to target
// nums = [0, 2, 2, 2, 3, 4, 5], target = 2 return 1
LOWER_BOUND(nums, target)
left, right = 0, nums.length
while left < right
mid = left + (right - left) // 2
if VALID(nums[mid], target)
right = mid
else
left = mid + 1
return left
VALID(num, target)
if num >= target
return True
return False
class Solution:
def lower_bound(self, nums: List[int], target: int) -> int:
def valid(num, target):
if num >= target:
return True
return False
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if valid(nums[mid], target):
right = mid
else:
left = mid + 1
return left
class Solution {
private boolean valid(int num, int target) {
if (num >= target) {
return true;
}
return false;
}
public int lowerBound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = ((right - left) >> 1) + left;
if (valid(nums[mid], target)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
class Solution {
private:
bool valid(int num, int target) {
if (num >= target) {
return true;
}
return false;
}
public:
int lowerBound(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = ((right - left) >> 1) + left;
if (valid(nums[mid], target)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};
Return the index of first element greater to target
// nums = [0, 2, 2, 2, 3, 4, 5], target = 2 return 4
UPPER_BOUND(nums, target)
// loop invariant: first valid element ∈ [left, right)
left, right = 0, nums.length
while left < right
mid = left + (right - left) // 2
if VALID(nums[mid], target)
right = mid
else
left = mid + 1
return left
VALID(num, target)
// the only different between LOWER_BOUND and UPPER_BOUND
if num > target
return True
return False
class Solution:
def upper_bound(self, nums: List[int], target: int) -> int:
def valid(num, target):
if num > target:
return True
return False
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if valid(nums[mid], target):
right = mid
else:
left = mid + 1
return left
class Solution {
private boolean valid(int num, int target) {
if (num > target) {
return true;
}
return false;
}
public int upperBound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = ((right - left) >> 1) + left;
if (valid(nums[mid], target)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
class Solution {
private:
bool valid(int num, int target) {
if (num > target) {
return true;
}
return false;
}
public:
int upperBound(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = ((right - left) >> 1) + left;
if (valid(nums[mid], target)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};