Leetcode Flashcards
Trapping Rain water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Use 2 pointer
check condition for the next element of both left and right individullay.
- Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Idea: Use binary search for finding correct partition.
x1 x2 x3 | x4 x5 x6 *
y1 y2 y3 y4 | y5 y6 y7 y8
correct partition would be such that
x3 <= y5 and y4 <= x4
- Merge k Sorted Lists
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6
In this problem , I’ll be adding all the k lists to the priority queue and simply construct a new final list by removing elements from the priority queue. This list will be the merged sorted list.
- Word Search
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
Output: true
Here we will be using depth first search at each index in board and will make a visited array to keep track if index has been visited already and also we will write a recursive dfs function with base case that if we reach the end of string we return true we need to consider five edge cases :
a) The fist char matches and there are no chars left in string then
b) We are at the right edge of board so can not move right
c) We are at the left edge of board so can not move left
d) We are at the bottom edge of board so can not move down
e) We are at the top edge of board so can not move up
Pairs of Songs With Total Durations Divisible by 60
You are given a list of songs where the ith song has a duration of time[i] seconds.
Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.
Input: time = [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60
Use HashMap
if (time[i] + time[j]) % 60 == 0. Save reminder of all numbers % 60 in hashmap R1=t1%60 R2=t2%60 R2=60-R1 t2=(60-t1%60)%60
Range Addition
You are given an integer length and an array updates where updates[i] = [startIdxi, endIdxi, inci].
You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the ith operation, you should increment all the elements arr[startIdxi], arr[startIdxi + 1], …, arr[endIdxi] by inci.
Return arr after applying all the updates
Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]
We update the value at start index, because it will be used in the future when we are adding up the values for the sum at each index between start index and end index (both inclusive). We update the negative value at the end index + 1, because the positive value of it should be only added at its previous indices (from start index to end index). Thus, when we accumulate the sum at the end for each index, we will get the correct values for each index.
- Design Tic-Tac-Toe
Implement the TicTacToe class:
TicTacToe(int n) Initializes the object the size of the board n. int move(int row, int col, int player) Indicates that the player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move.
- Have arrays rows and cols with size n and two variables diagonal and antidiagonal
- choose the player +1 or -1 and add them to rows and columns
- Check condition for diagonal(row==col) and antidiagonal(row==n-col-1) and add them accordingly
- Check if the value is equal the n and return accordingly
Word Break
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Input: s = “leetcode”, wordDict = [“leet”,”code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.
Use DP
Create a DP array with length of string size+1
for(int i=1;i
Course Schedule
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
// Find the number of dependency for each course // update in hash the course that are dependant on each course // Add the course with 0 dependency in queue // to keep track of courses completed keep a count //When polled increase count and decrease the dependency for that course //and course to queue if dependency in 0
Flip String to Monotone Increasing
A binary string is monotone increasing if it consists of some number of 0’s (possibly none), followed by some number of 1’s (also possibly none).
You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.
Return the minimum number of flips to make s monotone increasing.
Input: s = “00110”
Output: 1
Explanation: We flip the last digit to get 00111.
- We can have all 0’s or all 1’s or 1’s after 0’s
- So when we encounter 0 we can either flip it or flips the 1’s
- we keep track of no. of flips(which are zero essentially) and number of ones and flip the minimum number
Flip String to Monotone Increasing
A binary string is monotone increasing if it consists of some number of 0’s (possibly none), followed by some number of 1’s (also possibly none).
You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.
Return the minimum number of flips to make s monotone increasing.
Input: s = “00110”
Output: 1
Explanation: We flip the last digit to get 00111.
- We can have all 0’s or all 1’s or 1’s after 0’s
- So when we encounter 0 we can either flip it or flips the 1’s
- we keep track of no. of flips(which are zero essentially) and number of ones and flip the minimum number
Maximum Average Subtree
Given the root of a binary tree, return the maximum average value of a subtree of that tree. Answers within 10-5 of the actual answer will be accepted.
A subtree of a tree is any node of that tree plus all its descendants.
The average value of a tree is the sum of its values, divided by the number of nodes.
private int[] helper(TreeNode root){
if(root==null)
return new int[]{0,0};
int[] left=helper(root.left);
int[] right=helper(root.right);
int number=left[0]+right[0]+1;
int sum=left[1]+right[1]+root.val;
average=Math.max(average,(double)sum/number);
return new int[]{number,sum};
}
.All Nodes Distance K in Binary Tree
Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.
You can return the answer in any order.
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.
- Use BFS
- have a hashmap that has all the parent of the node
- maintain a set to keep track of seen nodes
- check the left,right and parent of node are seen and add in queue
- check if the level matches with the K levels
- when matched return all nodes in queue
Connecting Cities With Minimum Cost
There are n cities labeled from 1 to n. You are given the integer n and an array connections where connections[i] = [xi, yi, costi] indicates that the cost of connecting city xi and city yi (bidirectional connection) is costi.
Return the minimum cost to connect all the n cities such that there is at least one path between each pair of cities. If it is impossible to connect all the n cities, return -1,
The cost is the sum of the connections’ costs used.
Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.
-Use prims algorithm using priority queue
Snakes and Ladders
class Solution {
public int snakesAndLadders(int[][] board) {
int n=board.length;
int m=n*n;
int[] moves=new int[m];
int r=n-1,c=0,idx=0,even=0;
while(r>=0 && c>=0){
if(board[r][c]!=-1)
moves[idx]=board[r][c]-1;
else
moves[idx]=-1;
idx++;
if(even%2==0){
c++;
}
else{
c--;
}
if(c >= n){
c--;
even++;
r--;
}
else if(c<0){
even++;
r--;
c++;
}
}
int min=0;
Queue q=new LinkedList<>();
q.add(0);
moves[0]=-2;
while(!q.isEmpty()){
int size=q.size();
for(int i=0;i-1){
q.add(moves[curr]);
}else{
q.add(curr);
}
moves[curr]=-2;
}
}
}
min++;
} return -1; } }
