You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
/*package whatever //do not write package name here */
import java.io.*;
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public class GFG {
private ListNode mergeLists(ListNode l1, ListNode l2) {
if (l1 == null)
return l2;
if (l2 == null)
return l1;
ListNode dummyNode = new ListNode(-1);
ListNode resultIterator = dummyNode;
ListNode l1Iterator = l1;
ListNode l2Iterator = l2;
while (l1Iterator != null && l2Iterator != null) {
if (l1Iterator.val < l2Iterator.val) {
resultIterator.next = l1Iterator;
resultIterator = resultIterator.next;
l1Iterator = l1Iterator.next;
} else {
resultIterator.next = l2Iterator;
resultIterator = resultIterator.next;
l2Iterator = l2Iterator.next;
}
}
if (l1Iterator != null)
resultIterator.next = l1Iterator;
if (l2Iterator != null)
resultIterator.next = l2Iterator;
return dummyNode.next;
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0)
return null;
return mergeKListsUtility(lists, 0, lists.length - 1);
}
private ListNode mergeKListsUtility(ListNode[] lists, int low, int high) {
if (low > high)
return null;
else if (low == high)
return lists[low];
else {
int mid = low + (high - low) / 2;
ListNode left = mergeKListsUtility(lists, low, mid);
ListNode right = mergeKListsUtility(lists, mid + 1, high);
return mergeLists(left, right);
}
}
public static void main(String[] args) {
// Create test linked lists
ListNode list1 = new ListNode(1);
list1.next = new ListNode(4);
list1.next.next = new ListNode(5);
ListNode list2 = new ListNode(1);
list2.next = new ListNode(3);
list2.next.next = new ListNode(4);
ListNode list3 = new ListNode(2);
list3.next = new ListNode(6);
// Create an instance of GFG class
GFG gfg = new GFG();
// Create an array of linked lists
ListNode[] lists = {list1, list2, list3};
// Merge the lists
ListNode mergedList = gfg.mergeKLists(lists);
// Print the merged list
while (mergedList != null) {
System.out.print(mergedList.val + " ");
mergedList = mergedList.next;
}
}
}
2) Jump Game I
class Solution {
public boolean canJump(int[] nums) {
int definiteDestination=nums.length-1;
for (int stepsInTheNewDestination=nums.length-2;
stepsInTheNewDestination>=0;
stepsInTheNewDestination--){
if(
nums[stepsInTheNewDestination]
+
stepsInTheNewDestination
>=
definiteDestination
)
definiteDestination=stepsInTheNewDestination;
}
return definiteDestination==0;
}
}
3) Jump Game II
class Solution {
public int jump(int[] nums) {
return jumpGameTwo(nums);
}
public static int jumpGameTwo(int[] jumpLogs) {
Integer[] logs = new Integer[jumpLogs.length]; // minimum jumps log array
// As the first is the initial position and last index is the destination.
logs[jumpLogs.length - 1] = 0;
// traverse from behind
for (int individualTile = jumpLogs.length - 2; individualTile >= 0; individualTile--) {
int stepsAvailableToJumpFromThisTile = jumpLogs[individualTile];
// traverse from that index to the steps it can go because of it's capacity
// And find that tiles in the reach of the present tile that has some value in logs array and not null, and if there are multiple values in the tiles that are reachable from the present tile then consider that
int minimumJumpsToReactDestinationFromPresentTile = Integer.MAX_VALUE;
for (int potentialReach = 1; potentialReach <= stepsAvailableToJumpFromThisTile && individualTile + potentialReach < jumpLogs.length; potentialReach++) {
if (logs[individualTile + potentialReach] != null && logs[individualTile + potentialReach] < minimumJumpsToReactDestinationFromPresentTile) {
minimumJumpsToReactDestinationFromPresentTile = logs[individualTile + potentialReach];
}
}
if (minimumJumpsToReactDestinationFromPresentTile != Integer.MAX_VALUE) {
logs[individualTile] = minimumJumpsToReactDestinationFromPresentTile + 1;
}
}
return logs[0];
}
}
4) Find Median from Data Stream
class MedianFinder {
private PriorityQueue<Integer> maxHeap = null;
private PriorityQueue<Integer> minHeap=null;
public MedianFinder() {
maxHeap=new PriorityQueue<Integer>((a,b)-> b-a);
minHeap=new PriorityQueue<Integer>((a,b)-> a-b);
}
public void addNum(int num) {
// start inserting element from the max heap
// check if the topmost element is greater than num in max heap then add num to the maxheap
// else add it to the min heap
// call the balance method to balance the number of nodes in each heap
if(maxHeap.size()==0||maxHeap.peek()>=num) maxHeap.offer(num);
else minHeap.offer(num);
// as min heap and max heap are global variables we dont need to pass the value
balanceMinHeapAndMaxHeapSizes();
}
private void balanceMinHeapAndMaxHeapSizes(){
if(maxHeap.size()-minHeap.size()>1) minHeap.offer(maxHeap.poll());
if(minHeap.size()-maxHeap.size()>1) maxHeap.offer(minHeap.poll());
}
public double findMedian() {
if(maxHeap.size()==minHeap.size()) return (maxHeap.peek()+minHeap.peek())/2.0;
if(maxHeap.size()>minHeap.size()) return maxHeap.peek();
if(maxHeap.size()<minHeap.size()) return minHeap.peek();
return 0.0;
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
5) House Rober 1
class Solution {
public int rob(int[] nums) {
// imagine if there are no house to rob
if(nums.length==0) return 0;
// imagine if we want to rob only 1 house
if(nums.length==1) return nums[0];
// imagine if there are only to robbable houses
if(nums.length==2) return Math.max(nums[0],nums[1]);
// imagine if there are more than 2 robbable house
int[] maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice=new int[nums.length];
maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[0]=nums[0];
maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[1]=Math.max(nums[0],nums[1]);
for(int i=2;i<nums.length;i++){
maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[i]/*Initializing valid rob entry with the sum of valid previous robs */=Math.max(
(maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[i-2]+nums[i])/*Safe rob possibility 1 */
,
(maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[i-1])/*Safe rob possibility 2 */
);
}
return maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[nums.length-1];
}
}
6) House Robbers II
class Solution {
public int rob(int[] nums) {
// imagine if there are no house to rob
if(nums.length==0) return 0;
// imagine if we want to rob only 1 house
if(nums.length==1) return nums[0];
// imagine if there are only to robbable houses
if(nums.length==2) return Math.max(nums[0],nums[1]);
// imagine if there are more than 2 robbable house
int[] numsWithoutFirst = new int[nums.length - 1];
int[] numsWithoutLast = new int[nums.length - 1];
// Copy nums array without the first element
System.arraycopy(nums, 1, numsWithoutFirst, 0, nums.length - 1);
// Copy nums array without the last element
System.arraycopy(nums, 0, numsWithoutLast, 0, nums.length - 1);
return Math.max(houseRoberOne(numsWithoutFirst), houseRoberOne(numsWithoutLast));
}
public int houseRoberOne(int[] nums) {
// imagine if there are no house to rob
if(nums.length==0) return 0;
// imagine if we want to rob only 1 house
if(nums.length==1) return nums[0];
// imagine if there are only to robbable houses
if(nums.length==2) return Math.max(nums[0],nums[1]);
// imagine if there are more than 2 robbable house
int[] maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice=new int[nums.length];
maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[0]=nums[0];
maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[1]=Math.max(nums[0],nums[1]);
for(int i=2;i<nums.length;i++){
maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[i]/*Initializing valid rob entry with the sum of valid previous robs */=Math.max(
(maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[i-2]+nums[i])/*Safe rob possibility 1 */
,
(maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[i-1])/*Safe rob possibility 2 */
);
}
return maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[nums.length-1];
}
}
7) Top K frequent elements
import java.util.*;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// Create a map to store the frequency of each number
Map<Integer, Integer> frequencyMap = new HashMap<>();
for (int num : nums) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
// Create a priority queue to store ElementLog objects
PriorityQueue<ElementLog> pq = new PriorityQueue<>(new ElementLogsComparator());
// Iterate over the frequency map and add elements to the priority queue
for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
int element = entry.getKey();
int frequency = entry.getValue();
pq.offer(new ElementLog(element, frequency));
if (pq.size() > k) {
pq.poll();
}
}
// Create a result array and populate it with the top k frequent elements
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--) {
result[i] = pq.poll().getElement();
}
return result;
}
}
class ElementLogsComparator implements Comparator<ElementLog> {
@Override
public int compare(ElementLog element1, ElementLog element2) {
return Integer.compare(element1.getFrequency(), element2.getFrequency());
}
}
class ElementLog {
private int element;
private int frequency;
public ElementLog(int element, int frequency) {
this.element = element;
this.frequency = frequency;
}
public int getElement() {
return element;
}
public int getFrequency() {
return frequency;
}
}
8) Sum two integers
class Solution {
public int getSum(int a, int b) {
// 1 0 0 1 | a = 9
// 1 0 1 1 | b = 11
// 0 0 1 0 | XOR
// 1 0 0 1 | AND
// 1 0 0 1 0 | a&b << 1
//now add (a&b << 1) and XOR a,b
//now to add them again using xor and left shift we need to repeat that again till there is no carray left
while(b !=0 ) {
int temporaryCarry=(a&b)<<1;
a = a ^ b;// xor does add the number but doesnt take care of the carry
b = temporaryCarry;
}
// we are storing the result in a and carry in b
return a;
}
}
9) Number of 1 Bits
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int countNumberOfOnes=0;
while(n!=0){
// if last digit is 1 count one and right shift until entire number becomes 0.
/* countNumberOfOnes+=n%2;
n=n>>1;
*/
// secondly we can subtract 1 from the original number so we are basically subtracting a bit
n&=(n-1);
countNumberOfOnes++;
}
return countNumberOfOnes;
}
}
10) Counting bits
class Solution {
public int[] countBits(int n) {
int[] dp=new int[n+1];
int offset=1;
for(int i=1;i<=n;i++){
if((offset*2)==i) offset=i;
dp[i]=1+dp[i-offset];
}
return dp;
}
}
10) Minimum window sub-string
class Solution
{
public String minWindow (String s, String t)
{
return minimumWindowSubstring (s, t);
}
public static String minimumWindowSubstring (String completeString,
String subString)
{
String result = "";
HashMap < Character, Integer > frequencySubStringMap = new HashMap <> ();
for (int i = 0; i < subString.length (); i++)
{
char character = subString.charAt (i);
frequencySubStringMap.put (character,
frequencySubStringMap.
getOrDefault (character, 0) + 1);
}
int matchCount = 0; // number of counts of characters being considered in substring
int desiredMatchCount = subString.length ();
HashMap < Character, Integer > frequencyCompleteStringMap =
new HashMap <> ();
int i = -1;
int j = -1;
while (true)
{
boolean flag1 = false;
boolean flag2 = false;
// Acquire elements
while (i < completeString.length () - 1
&& matchCount < desiredMatchCount)
{
i++; // Until the matchCount is less than the desired matchCount
char ch = completeString.charAt (i);
frequencyCompleteStringMap.put (ch,
frequencyCompleteStringMap.
getOrDefault (ch, 0) + 1);
if (frequencyCompleteStringMap.getOrDefault (ch, 0) <=
frequencySubStringMap.getOrDefault (ch, 0))
{
matchCount++;
}
flag1 = true;
}
// Collect answers and release
while (j < i && matchCount == desiredMatchCount)
{
String potentialResult = completeString.substring (j + 1, i + 1);
if (result.length () == 0
|| potentialResult.length () < result.length ())
{
result = potentialResult;
}
j++;
char ch = completeString.charAt (j);
if (frequencyCompleteStringMap.get (ch) == 1)
{
frequencyCompleteStringMap.remove (ch);
}
else
{
frequencyCompleteStringMap.put (ch,
frequencyCompleteStringMap.
get (ch) - 1);
}
if (frequencyCompleteStringMap.getOrDefault (ch, 0) <
frequencySubStringMap.getOrDefault (ch, 0))
{
matchCount--;
}
flag2 = true;
}
if (!flag1 && !flag2)
{
break;
}
}
return result;
}
}
11) Reverse bits
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int result=0;
for(int i=0;i<32;i++){
result<<=1;//left shift result
if((n&1)==1)// to check whether last bit is one or 0
//if one
result++; // add that last bit of n to result and int the next iteration it will be right shifted and will be gone to right place to reveres bits
//now right shift the number
n>>=1;
}
return result;
}
}
12) Missing number
class Solution {
public int missingNumber(int[] nums) {
//the principle here is if we xor number with 0 we get number itself
//and if we xor number with itself we get 0
int result = nums.length;
int xor1=0;
int xor2=0;
for (int i = 0; i <=nums.length; i++) {
xor1^=i;
} // as we are given all the numbers will fall in the range of 0 to nums.length
for (int i = 0; i < nums.length; i++) {
xor2^=nums[i];
}
//all the numbers that exist will cancel each other and only the one left will be the missing one
return xor1^xor2;
}
}
13) Decode ways
class Solution {
public int numDecodings(String s) {
if (s.length() == 1) {
if (s.charAt(0) == '0')
return 0;
}
int[] dp = new int[s.length()];
dp[0] = 1;
if (s.length() >= 2) {
if (s.charAt(0) == '0')
return 0;
}
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i - 1) == '0' && s.charAt(i) == '0') {
dp[i] = 0;
} else if (s.charAt(i - 1) == '0' && s.charAt(i) != '0') {
dp[i] = dp[i - 1];
} else if (s.charAt(i - 1) != '0' && s.charAt(i) == '0') {
if (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2')
dp[i] = (i >= 2 ? dp[i - 2] : 1);
else
dp[i] = 0;
} else if (s.charAt(i - 1) != '0' && s.charAt(i) != '0') {
if (Integer.parseInt(s.substring(i - 1, i + 1)) <= 26)
dp[i] = dp[i - 1] + (i >= 2 ? dp[i - 2] : 1);
else
dp[i] = dp[i - 1];
}
}
return dp[s.length() - 1];
}
}
14) Alien Dictionary
class Solution
{
public String findOrder(String [] dict, int N, int K)
{
// Write your code here
return alienOrder(dict);
}
public String alienOrder(String[] words) {
HashMap<Character, HashSet<Character>> map = new HashMap<>();
HashMap<Character, Integer> indegree = new HashMap<>();
for (String st : words) {
for (char ch : st.toCharArray()) {
indegree.put(ch, 0);
}
}
for (int i = 0; i < words.length - 1; i++) {
String curr = words[i];
String next = words[i + 1];
boolean mismatchFlag = false;
int len = Math.min(curr.length(), next.length());
for (int j = 0; j < len; j++) {
char ch1 = curr.charAt(j);
char ch2 = next.charAt(j);
if (ch1 != ch2) {// then we can derive conclusion regarding which character will be before which
// character
HashSet<Character> set = new HashSet<>();
if (map.containsKey(ch1) == true) {
set = map.get(ch1);
if (set.contains(ch2) == false) {
set.add(ch2);
indegree.put(ch2, indegree.get(ch2) + 1);
map.put(ch1, set);
}
} else {
// if adjacency list doesnt contain ch2
set.add(ch2);
indegree.put(ch2, indegree.get(ch2) + 1);
map.put(ch1, set);
}
mismatchFlag = true;
break;
}
}
if (mismatchFlag == false && curr.length() > next.length()) {
return "";
}
}
// topological sort
LinkedList<Character> queue = new LinkedList<>();
StringBuilder ans = new StringBuilder();
// add those characters who have indegree zero
for (char ch : indegree.keySet()) {
if (indegree.get(ch) == 0)
queue.addLast(ch);
}
int count = 0;
while (queue.size() != 0) {
Character rem = queue.removeFirst();
ans.append(rem);
count++;
if (map.containsKey(rem) == true) {
HashSet<Character> nbrs = map.get(rem);
for (char nbr : nbrs) {
indegree.put(nbr, indegree.get(nbr) - 1);
if (indegree.get(nbr) == 0) {
queue.addLast(nbr);
}
}
}
}
if (count == indegree.size())
return ans.toString();
return "";
}
}
15) Graph valid tree
class Solution {
/**
* @param n: An integer
* @param edges: a list of undirected edges
* @return: true if it's a valid tree, or false
*/
public boolean validTree(int n, int[][] edges) {
// If there is no graph to traverse, we will return true
if (n == 0) {
return true;
}
List<List<Integer>> adjacencyList = new ArrayList<>();
for (int i = 0; i < n; i++) {
adjacencyList.add(new ArrayList<>());
}
// Create an adjacency list of an undirected graph
for (int[] edge : edges) {
int node1 = edge[0];
int node2 = edge[1];
adjacencyList.get(node1).add(node2);
adjacencyList.get(node2).add(node1);
}
Set<Integer> visitedVertices = new HashSet<>();
// Call the depth-first search helper method
//we have taken initial node as 0 because we know that nodes are from 0 to n-1
return depthFirstSearch(adjacencyList, visitedVertices, 0, -1) && n == visitedVertices.size();
}
private boolean depthFirstSearch(List<List<Integer>> adjacencyList, Set<Integer> visitedVertices, int nodeForDepthFirstSearchTraversal, int previousNode) {
if (visitedVertices.contains(nodeForDepthFirstSearchTraversal)) {
// If the current node is in the set of visited vertices, return false
return false;
}
visitedVertices.add(nodeForDepthFirstSearchTraversal); // Add the current node to the visited vertices set
for (int neighbor : adjacencyList.get(nodeForDepthFirstSearchTraversal)) {
if (neighbor == previousNode) {
// Do not apply DFS to the parent (previous) node
continue;
}
// If the below condition returns false, it means there is a cycle, so return false
if (!depthFirstSearch(adjacencyList, visitedVertices, neighbor, nodeForDepthFirstSearchTraversal)) {
return false;
}
}
// If there is no cycle, return true
return true;
}
}
16) Number of connect component in an undirected graph
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Java {
private static int[] parent;
private static int[] rank;
public static int numberOfLooselyConnectedComponents(int n, List<List<Integer>> edges) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
int count = n;
for (List<Integer> edge : edges) {
int node1 = edge.get(0);
int node2 = edge.get(1);
count -= unionFind(node1, node2);
}
return count;
}
private static int unionFind(int node1, int node2) {
int rootParentOfNode1 = findRootParent(node1);
int rootParentOfNode2 = findRootParent(node2);
if (rootParentOfNode1 == rootParentOfNode2) {
return 0;
}
if (rank[rootParentOfNode1] < rank[rootParentOfNode2]) {
parent[rootParentOfNode1] = rootParentOfNode2;
rank[rootParentOfNode2] += rank[rootParentOfNode1];
} else {
parent[rootParentOfNode2] = rootParentOfNode1;
rank[rootParentOfNode1] += rank[rootParentOfNode2];
}
return 1;
}
private static int findRootParent(int node) {
int result = node;
while (result != parent[result]) {
parent[result] = parent[parent[result]];
result = parent[result];
}
return result;
}
public static void main(String[] args) {
List<List<Integer>> edges = new ArrayList<>();
edges.add(Arrays.asList(0, 1));
edges.add(Arrays.asList(1, 2));
edges.add(Arrays.asList(3, 4));
edges.add(Arrays.asList(2, 4));
edges.add(Arrays.asList(5, 6));
edges.add(Arrays.asList(4, 4));
edges.add(Arrays.asList(5, 6));
int n = 7;
int componentCount = numberOfLooselyConnectedComponents(n, edges);
System.out.println("Number of components: " + componentCount);
}
}
17) Longest consecutive sequence
import java.util.Arrays;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = Arrays.stream(nums)
.boxed()
.collect(Collectors.toSet());
AtomicInteger longestConsecutiveArraySize = new AtomicInteger(0);
if (set.size() == 1) return 1;
if (set.isEmpty()) return 0;
set.parallelStream().forEach(each -> {
if (!set.contains(each - 1)) {
int consecutiveArraySizeCount = 1;
int currentElement = each;
while (set.contains(currentElement + 1)) {
consecutiveArraySizeCount++;
currentElement++;
}
// if we would have used simple integer then it would have thrown this error
/*
Line 27: error: local variables referenced from a lambda expression must be final or effectively final
longestConsecutiveArraySize=Math.max(longestConsecutiveArraySize,consecutiveArraySizeCount);
^
Line 27: error: local variables referenced from a lambda expression must be final or effectively final
longestConsecutiveArraySize=Math.max(longestConsecutiveArraySize,consecutiveArraySizeCount);
^
*/
longestConsecutiveArraySize.set(Math.max(longestConsecutiveArraySize.get(), consecutiveArraySizeCount));
}
});
return longestConsecutiveArraySize.get();
}
}
18) Clone graph
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
class Solution {
public Node cloneGraph(Node node) {
if(node==null) return null;
// create a hashmap that indicates, node value of original node has an object created Copy of the type Node
Map<Integer, Node>map=new HashMap<>();
return cloneGraph(node, map);
}
private Node cloneGraph(Node node, Map<Integer, Node> map){
if(map.containsKey(node.val)) return map.get(node.val);
Node copy=new Node(node.val);
map.put(node.val,copy);
for(Node neighbor: node.neighbors) copy.neighbors.add(cloneGraph(neighbor, map));
return copy;
}
}
19) Maximum depth of a binary tree
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int maxDepth(TreeNode root) {
// Using switch statement to choose between recursive and iterative approach
String approach="iterative";
switch (approach) {
case "recursive":
return maxDepthRecursive(root);
case "iterative":
return maxDepthIterative(root);
default:
throw new IllegalArgumentException("Invalid approach specified");
}
}
// Recursive approach
private int maxDepthRecursive(TreeNode root) {
return root == null ? 0 : Math.max(maxDepthRecursive(root.left), maxDepthRecursive(root.right)) + 1;
}
// Iterative approach
private int maxDepthIterative(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
depth++;
}
return depth;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(Objects.isNull(root)) return root;
invertTree(root.left);
invertTree(root.right);
TreeNode temporary=root.left;
root.left=root.right;
root.right=temporary;
return root;
}
}
22) Unique paths
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp=new int[m][n];
for(int i=0;i<m;i++) dp[i][0]=1; // initialize the leftmost columns by 1 as there is only 1 way
for(int i=0;i<n;i++) dp[0][i]=1; // initalize the topmost row by 1 as tehre is only 1 way
for(int i=1;i<m;i++)for(int j=1;j<n;j++){
dp[i][j]=dp[i-1][j]+dp[i][j-1];// traverse all the columns
}
return dp[m-1][n-1];
}
}
23) Combination sum 4
class Solution {
Map<Integer, Integer> map=new HashMap<>(); // key would be the target value and value would be sum of combination count
public int combinationSum4(int[] nums, int target) {
return combinationSum4Utility(nums, target);
}
private int combinationSum4Utility(int[] nums, int target){
if(map.containsKey(target)) return map.get(target);
if(target==0) return 1;
else if(target<0) return 0;
else{
int possibleWays=0;
for(int element: nums) possibleWays+=combinationSum4Utility(nums, target-element);
map.put(target, possibleWays);
return possibleWays;
}
}
}
24) Combination sum
/**
* CombinationSum problem is the principle of backtracking
*
* 1) maintain the current state
* 2) Loop through all the possible sample set
* 3) Add new element from the sampleset
* 4) Recursively invoke for the next entry
* 5) Remove the last element that was added in the sample set
*
* @param candidates[] number of elements in the array
* @param target sum that we want to achieve
* @return returns the list of lists that sums to the target
*/
class Solution {
List<List<Integer>> result=new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if(candidates.length==0) return result;
combinationSumUtility(candidates, target, 0,new ArrayList<Integer>(),0);
return result;
}
private void combinationSumUtility(
int[] candidates,
int target,
int currSum, // current sum that we are currently at
List<Integer> subList, // initially no element has been added to it
int index// index over which we are currently looking for
)
{
if((index>=candidates.length)||(currSum>target)) return;
if(currSum==target) {
result.add(new ArrayList<>(subList));
return;
}
for(int i=index;i<candidates.length;i++){
subList.add(candidates[i]);
combinationSumUtility(candidates, target, currSum + candidates[i],subList, i);
subList.remove(subList.size()-1);
}
}
}
25) Longest common subsequence
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int len1=text1.length();
int len2=text2.length();
if(text1.equals(text2)) return len1;
int[][] dp=new int[len1+1][len2+1];
for(int i=1;i<=len1;i++)for(int j=1;j<=len2;j++){
if(text1.charAt(i-1)==text2.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
return dp[len1][len2];
}
}
26) Longest increasing subsequence
import java.util.Arrays;
class Solution {
public int lengthOfLIS(int[] nums) {
int[] lis = new int[nums.length];
Arrays.fill(lis, 1); // Initialize lis array with 1 as the minimum length of LIS for each element is 1
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
lis[i] = Math.max(lis[i], lis[j] + 1);
}
}
}
Arrays.sort(lis);
return lis[nums.length - 1];
}
}
27) Word break problem
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// store the worddict in a set
Set<String> word_dictionary_set = new HashSet<>(wordDict);
// create a `dp` array of size s.length()
boolean[] dp = new boolean[s.length() + 1];
// only the first index of the `dp` array is kept as True,
// since the null string will
// always be present in the dictionary.
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
// check if dp[j] is True, and if it is True,
// also check if the substring `s[i:j]` is
// present in the dictionary or not.
if (dp[j] && word_dictionary_set.contains(s.substring(j, i))) {
// If `s[i:j]` is present,
// mark `dp[i]` as `True`
// and break from the loop
dp[i] = true;
break;
}
}
}
// Return the value present at the
// nth index of the `dp` array, either true or false
for(boolean i: dp) System.out.println(i);
return dp[s.length()];
}
}
28) Coin change
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (i - coins[j] >= 0 && dp[i - coins[j]] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] != Integer.MAX_VALUE ? dp[amount] : -1;
}
}
29) Climbing Stairs
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
30) Course schedule
import java.util.ArrayList;
import java.util.List;
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// Step 1: Create an adjacency list to represent the graph
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
// Step 2: Populate the adjacency list with prerequisite relationships
for (int[] pre : prerequisites) {
adj.get(pre[1]).add(pre[0]);
}
// Step 3: Initialize boolean arrays for visited nodes and nodes in the current path
boolean[] visited = new boolean[numCourses];
boolean[] inStack = new boolean[numCourses];
// Step 4: Iterate over each course and perform a depth-first search
for (int i = 0; i < numCourses; i++) {
if (dfs(i, adj, visited, inStack)) {
return false;
}
}
return true;
}
// Depth-first search (DFS) function
private boolean dfs(int node, List<List<Integer>> adj, boolean[] visited, boolean[] inStack) {
// Step 5: Check if the current node is already in the current path
if (inStack[node]) {
return true; // A cycle is detected
}
if (visited[node]) {
return false; // No cycle in the current path, already visited
}
visited[node] = true; // Mark the current node as visited
inStack[node] = true; // Add the current node to the current path
// Step 8: Iterate over neighbors and recursively call the DFS function
for (int neighbor : adj.get(node)) {
if (dfs(neighbor, adj, visited, inStack)) {
return true; // A cycle is detected in the neighbors
}
}
inStack[node] = false; // Remove the current node from the current path
return false; // No cycle found in the current path
}
}
31) Pacific atlantic water flow
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> pacificAtlantic(int[][] heights) {
List<List<Integer>> ans = new ArrayList<>();
int m = heights.length;
int n = heights[0].length;
boolean[][] pacific = new boolean[m][n];
boolean[][] atlantic = new boolean[m][n];
// Traverse the first and last rows
for (int j = 0; j < n; j++) {
dfs(0, j, pacific, heights, Integer.MIN_VALUE);
dfs(m - 1, j, atlantic, heights, Integer.MIN_VALUE);
}
// Traverse the first and last columns
for (int i = 0; i < m; i++) {
dfs(i, 0, pacific, heights, Integer.MIN_VALUE);
dfs(i, n - 1, atlantic, heights, Integer.MIN_VALUE);
}
// Check the cells that can reach both the Pacific and Atlantic oceans
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
List<Integer> indexes = new ArrayList<>();
indexes.add(i);
indexes.add(j);
ans.add(indexes);
}
}
}
return ans;
}
private void dfs(int i, int j, boolean[][] canReach, int[][] matrix, int prevHeight) {
int m = matrix.length;
int n = matrix[0].length;
// Check for out of bounds conditions or if the cell has already been visited
if (i < 0 || j < 0 || i >= m || j >= n || canReach[i][j] || matrix[i][j] < prevHeight)
return;
// Mark the cell as reachable
canReach[i][j] = true;
// Recursively explore all four directions
dfs(i - 1, j, canReach, matrix, matrix[i][j]); // Up
dfs(i + 1, j, canReach, matrix, matrix[i][j]); // Down
dfs(i, j - 1, canReach, matrix, matrix[i][j]); // Left
dfs(i, j + 1, canReach, matrix, matrix[i][j]); // Right
}
}
32) Number of islands
class Solution {
public int numIslands(char[][] grid) {
int res = 0; // Variable to store the result (number of islands)
// Iterate through each cell in the grid
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
// If the cell contains '1', it is part of an island
if (grid[i][j] - '0' == 1) {
res++; // Increment the island count
dfs(grid, i, j); // Call the depth-first search function to mark all connected cells as visited
}
}
}
return res; // Return the number of islands
}
// Depth-first search function to mark all connected cells as visited
void dfs(char[][] grid, int i, int j) {
// Check if the current cell is within the grid boundaries and contains '1'
if (i >= 0 && j >= 0 && i < grid.length && j < grid[0].length && grid[i][j] - '0' == 1) {
grid[i][j] = '0'; // Mark the current cell as visited by changing its value to '0'
// Recursively call dfs on the adjacent cells (up, down, left, right)
dfs(grid, i + 1, j); // Down
dfs(grid, i - 1, j); // Up
dfs(grid, i, j + 1); // Right
dfs(grid, i, j - 1); // Left
}
}
}
32) Binary tree level order traversal
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (Objects.isNull(root)) return result;
Queue<TreeNode> levelNodes = new LinkedList<>();
levelNodes.add(root);
while (!levelNodes.isEmpty()) {
int levelSize = levelNodes.size();
List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode current = levelNodes.poll();
currentLevel.add(current.val);
if (Objects.nonNull(current.left)) {
levelNodes.add(current.left);
}
if (Objects.nonNull(current.right)) {
levelNodes.add(current.right);
}
}
result.add(currentLevel);
}
return result;
}
}
33) Serialize and deserialize the binary tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Serialize
public String serialize(TreeNode root) {
// Check if the current node is null
if (root == null) {
// If it is null, return "null," to represent a null node
return "null,";
}
// Serialize the left subtree recursively
String leftSerialized = serialize(root.left);
// Serialize the right subtree recursively
String rightSerialized = serialize(root.right);
// Combine the current node value, left subtree serialization, and right subtree serialization
return root.val + "," + leftSerialized + rightSerialized;
}
// Deserialize
public TreeNode deserialize(String data) {
// Split the serialized data by commas and create a queue to process nodes
Queue<String> nodesLeft = new LinkedList<>(Arrays.asList(data.split(",")));
// Start the deserialization process by calling the helper function
return deserializeHelper(nodesLeft);
}
// Helper function for deserialization
public TreeNode deserializeHelper(Queue<String> nodesLeft) {
// Dequeue the next value from the queue
String valueForNode = nodesLeft.poll();
// If the value represents a null node, return null
if (valueForNode.equals("null")) {
return null;
}
// Create a new TreeNode with the parsed integer value
TreeNode newNode = new TreeNode(Integer.parseInt(valueForNode));
// Recursively deserialize the left subtree and set it as the left child
newNode.left = deserializeHelper(nodesLeft);
// Recursively deserialize the right subtree and set it as the right child
newNode.right = deserializeHelper(nodesLeft);
// Return the current node
return newNode;
}
// Example:
// Let's use the binary tree: 1
// / \
// 2 3
// / \
// 4 5
// Serialization:
// - serialize(root) is called with the root node (value 1)
// - serialize(root.left) is called with the left subtree (node with value 2)
// - serialize(null) is called for the left child of node 2
// - serialize(null) is called for the right child of node 2
// - serialize(root.right) is called with the right subtree (node with value 3)
// - serialize(root.left) is called with the left subtree (node with value 4)
// - serialize(null) is called for the left child of node 4
// - serialize(null) is called for the right child of node 4
// - serialize(root.right) is called with the right subtree (node with value 5)
// - serialize(null) is called for the left child of node 5
// - serialize(null) is called for the right child of node 5
// - The serialized result is "1,2,null,null,3,4,null,null,5,null,null,"
// Deserialization:
// - deserialize("1,2,null,null,3,4,null,null,5,null,null,") is called
// - deserializeHelper is called with the queue ["1", "2", "null", "null", "3", "4", "null", "null", "5", "null", "null"]
// - Dequeue "1" and create a node with value 1
// - Recursively call deserializeHelper for the left subtree
// - Dequeue "2" and create a node with value 2
// - Recursively call deserializeHelper for the left and right children of node 2 (both null)
// - Recursively call deserializeHelper for the right subtree
// - Dequeue "3" and create a node with value 3
// - Recursively call deserializeHelper for the left subtree
// - Dequeue "4" and create a node with value 4
// - Recursively call deserializeHelper for the left and right children of node 4 (both null)
// - Recursively call deserializeHelper for the right subtree
// - Dequeue "5" and create a node with value 5
// - Recursively call deserializeHelper for the left and right children of node 5 (both null)
// - The binary tree is successfully deserialized, and the root node with value 1 is returned
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
34) Implement trie
class Trie {
private TrieNode root;
private class TrieNode{
private TrieNode[] children = null;
private boolean isWord;
public TrieNode(){
children = new TrieNode[26];
}
}
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode it = root;
for(char c : word.toCharArray()) {
int indexInTrieNode = c - 'a';
if(it.children[indexInTrieNode] ==null){
it.children[indexInTrieNode] = new TrieNode();
}
it = it.children[indexInTrieNode];
}
it.isWord = true;
}
public boolean search(String word) {
TrieNode it = root;
for(char c : word.toCharArray()){
int indexInTrieNode = c - 'a';
if(it.children[indexInTrieNode] == null){
// no node was found
return false;
} else{
it = it.children[indexInTrieNode];
}
}
return it.isWord;
}
public boolean startsWith(String prefix) {
TrieNode it = root;
for(char c : prefix.toCharArray()){
int indexInTrieNode = c - 'a';
if(it.children[indexInTrieNode] == null){
return false;
} else{
it = it.children[indexInTrieNode];
}
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
35) Word Search 2
class Solution {
private class TrieNode {
private TrieNode[] children;
private String word;
TrieNode(){
children = new TrieNode[26];
}
}
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
TrieNode root = buildTrie(words);
int m= board.length, n = board[0].length;
// System.out.println(" Value is " + root.children['o' -'c']);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
dfs(board, i, j, root, res);
}
}
return res;
}
public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
char c = board[i][j];
if (c == ';' || p.children[c - 'a'] == null) return;
p = p.children[c - 'a'];
if (p.word != null) { // found one
res.add(p.word);
p.word = null; // de-duplicate
}
board[i][j] = ';';
if (i > 0) dfs(board, i - 1, j ,p, res);
if (j > 0) dfs(board, i, j - 1, p, res);
if (i < board.length - 1) dfs(board, i + 1, j, p, res);
if (j < board[0].length - 1) dfs(board, i, j + 1, p, res);
board[i][j] = c;
}
public TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode p = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (p.children[i] == null) p.children[i] = new TrieNode();
p = p.children[i];
}
p.word = w;
}
return root;
}
}
36) Subtree of another tree
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return false;
if (isSameTree(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
public boolean isSameTree(TreeNode root, TreeNode subRoot) {
if (root == null && subRoot == null) return true;
if (root == null || subRoot == null) return false;
if (root.val != subRoot.val) return false;
return isSameTree(root.left, subRoot.left) && isSameTree(root.right, subRoot.right);
}
}
37) Kth smallest element in BST
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int count = 0;
public int kthSmallest(TreeNode root, int k) {
return kthSmallestElementInorder(root, k).val;
}
public TreeNode kthSmallestElementInorder(TreeNode root, int k) {
if (root == null) return null;
TreeNode left = kthSmallestElementInorder(root.left, k);
if (left != null) return left;
count++;
if (count == k) return root;
return kthSmallestElementInorder(root.right, k);
}
}
38) Implement trie
class Trie {
private TrieNode root;
private class TrieNode{
private TrieNode[] children = null;
private boolean isWord;
public TrieNode(){
children = new TrieNode[26];
}
}
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode it = root;
for(char c : word.toCharArray()) {
int indexInTrieNode = c - 'a';
if(it.children[indexInTrieNode] ==null){
it.children[indexInTrieNode] = new TrieNode();
}
it = it.children[indexInTrieNode];
}
it.isWord = true;
}
public boolean search(String word) {
TrieNode it = root;
for(char c : word.toCharArray()){
int indexInTrieNode = c - 'a';
if(it.children[indexInTrieNode] == null){
// no node was found
return false;
} else{
it = it.children[indexInTrieNode];
}
}
return it.isWord;
}
public boolean startsWith(String prefix) {
TrieNode it = root;
for(char c : prefix.toCharArray()){
int indexInTrieNode = c - 'a';
if(it.children[indexInTrieNode] == null){
return false;
} else{
it = it.children[indexInTrieNode];
}
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
39) Add and serch word
class WordDictionary {
private class TrieNode {
private TrieNode[] children = null;
boolean isLeaf;
public TrieNode(){
children = new TrieNode[26];
}
}
private TrieNode root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
TrieNode it = root;
for(int i=0;i<word.length();i++){
char c = word.charAt(i);
int index = c -'a';
if(it.children[index]==null){
TrieNode newNode = new TrieNode();
it.children[index] = newNode;
}
it = it.children[index];
}
it.isLeaf = true;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
public boolean search(String word) {
return searchHelper(word, 0, root);
}
private boolean searchHelper(String word, int sIndex, TrieNode root){
if(word.length()==sIndex){
return root.isLeaf;
}
char c = word.charAt(sIndex);
if(c=='.'){
for(int i=0;i<26;i++){
if(root.children[i]!=null && searchHelper(word, sIndex+1, root.children[i])){
return true;
}
}
} else {
int index = c -'a';
if(root.children[index]!=null && searchHelper(word, sIndex+1, root.children[index])){
return true;
}
}
return false;
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
40) Validate binary search tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class ValidateBinarySearchTree {
// TC: O(n)
// SC:Height of tree
public boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean helper(TreeNode root, long min, long max){
if(root == null){
return true;
}
if(root.val<=min || root.val>=max){
return false;
}
return helper(root.left, min, root.val) && helper(root.right, root.val, max);
}
}
41) Construct Binary Tree from Preorder and Inorder Traversal
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) return null;
TreeNode root = new TreeNode(preorder[0]);
int mid = 0;
for (int i = 0; i < inorder.length; i++) {
if (preorder[0] == inorder[i]) mid = i;
}
root.left =
buildTree(
Arrays.copyOfRange(preorder, 1, mid + 1),
Arrays.copyOfRange(inorder, 0, mid)
);
root.right =
buildTree(
Arrays.copyOfRange(preorder, mid + 1, preorder.length),
Arrays.copyOfRange(inorder, mid + 1, inorder.length)
);
return root;
}
}
42) Lowest common ancestor of a binary search tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(
TreeNode root,
TreeNode p,
TreeNode q
) {
if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(
root.right,
p,
q
);
if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(
root.left,
p,
q
);
return root;
}
}
43) Two sum
import java.util.HashMap;
import java.util.Map;
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> valuesAndIndexes = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int remainingAmount = target - nums[i];
if (valuesAndIndexes.containsKey(remainingAmount)) {
return new int[]{valuesAndIndexes.get(remainingAmount), i};
}
valuesAndIndexes.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
public class Solution {
/**
* @param strs a list of strings
* @return encodes a list of strings to a single string.
*/
public String encode(List<String> strs) {
// Write your code here
StringBuilder ans = new StringBuilder();
for (String s : strs) {
for (char c : s.toCharArray()) {
if (c == ':') { // : itself
ans.append("::");
} else { //ordinary character
ans.append(c);
}
}
ans.append(":;"); // ; connector
}
return ans.toString();
}
/**
* @param str a string
* @return dcodes a single string to a list of strings
*/
public List<String> decode(String str) {
// Write your code here
List<String> ans = new ArrayList<>();
char[] sc = str.toCharArray();
StringBuilder item = new StringBuilder();
int i = 0;
while (i < str.length()) {
if (sc[i] == ':') { //escape
if (sc[i + 1] == ';') { // ; connector
ans.add(item.toString());
item = new StringBuilder();
i += 2;
} else { // : itself
item.append(sc[i + 1]);
i += 2;
}
} else { //ordinary character
item.append(sc[i]);
i += 1;
}
}
return ans;
}
}
45) Longest substring without repeating characters
class Solution {
public int lengthOfLongestSubstring(String S) {
int startPointer=0;
int endPointer=0;
int max=0;
HashSet<Character> hashSet=new HashSet<Character>();
while(endPointer<S.length()){
if(!hashSet.contains(S.charAt(endPointer))){
hashSet.add(S.charAt(endPointer));
endPointer++;
max=Math.max(hashSet.size(),max);
}
else{
hashSet.remove(S.charAt(startPointer));
startPointer++;
}
}
return max;
}
}
46) Lonmgest repeating character replacement
class Solution {
public int characterReplacement(String s, int k) {
return longest(s, k);
}
static int longest(String s, int k){
int N=s.length();
int [] charCount=new int[26];
int windowStart=0;
int maxLength=0;
int maxCount=0;
for(int windowEnd=0;windowEnd<N; windowEnd++){
charCount[s.charAt(windowEnd)-'A']++; // shows which characters are thgere in the window and their qantities
int currentCharCount=charCount[s.charAt(windowEnd)-'A'];
maxCount=Math.max(maxCount, currentCharCount);
// Now in which case will we shift the window to the right
while(windowEnd-windowStart-maxCount+1>k){ // windowEnd-windowStart-maxcount gives us the usual unmodified string winodow of repeating characters but then we are comparing it with the k elements that we can modify ourselves because we have access to modify k more elements and make them the same element that that was previously there in the window
// its then we shift the window with the hope that we will find a greater max count
charCount[s.charAt(windowStart)-'A']--;
windowStart++;
}
maxLength=Math.max(maxLength,windowEnd-windowStart+1);
}
return maxLength;
}}
47) Longest palindromic substring
class Solution {
public String longestPalindrome(String s) {
if (Objects.isNull(s) || s.length()<1) return ""; // if the string is empty or with just one element
int start=0; // start of index
int end=0; // end of index
for(int i=0; i<s.length(); i++){
// after every element traversal we will check if considering that element as center is ther ea liongest palkindromic substring
// there are two possibilities as if the number of elements in the palindrome are odd then there will be one element in the center while comapering right most and leftmost element and the usual case
int len1=checkForPalindromeFromTheMiddleElement(s,i,i);
int len2=checkForPalindromeFromTheMiddleElement(s,i,i+1);
int len=Math.max(len1, len2);
if(len>end-start){ // now as we know the length of the palindrome we will go back half the lenght to find start index
start=i-(len-1)/2;
// will will go front half the lenght toi find the end index of the longest palindrome presently
end=i+len/2;
}
}
return s.substring(start,end+1);
}
public int checkForPalindromeFromTheMiddleElement(String s, int left, int right){
if(s==null || left> right) return 0;
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
left--;
right++;
}
return right-left-1;
}
}
48) Palindromic substring
class Solution {
int result=0;
public int countSubstrings(String s) {
for( int i=0;i<s.length();i++){
checkForPalindromeFromTheMiddleElement(s, i, i);
checkForPalindromeFromTheMiddleElement(s, i, i+1);
}
return result;
}
public void checkForPalindromeFromTheMiddleElement(String s, int left, int right){
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
result++;
left--;
right++;
}
}
}
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null || head.next == null) return null;
ListNode temp = new ListNode(0);
temp.next = head;
ListNode first = temp, second = temp;
while (n > 0) {
second = second.next;
n--;
}
while (second.next != null) {
second = second.next;
first = first.next;
}
first.next = first.next.next;
return temp.next;
}
}
51) Valid Palindrome
class Solution {
public boolean isPalindrome(String s) {
//Using two pointers
String result="";
for (char c : s.toCharArray()) if(Character.isDigit(c) || Character.isLetter(c)) result+=c; // just to remove unnecessary punctuation or any other symbol
result=result.toLowerCase();
int start=0;
int end=result.length()-1;
while(start<=end){if(result.charAt(start)!=result.charAt(end)) return false; start++; end--;}
return true;
}
}
52) Meeting Rooms
/**
* Definition of Interval:
* public class Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* @param intervals: an array of meeting time intervals
* @return: if a person could attend all meetings
*/
public boolean canAttendMeetings(List<Interval> intervals) {
// Write your code here
//declare array to gather start time and end time seperately
int[] start=new int[intervals.size()];
int[] end=new int[intervals.size()];
for(int i=0;i<intervals.size(); i++){
start[i]=intervals.get(i).start;
end[i]=intervals.get(i).end;
}
//sort two arrays
Arrays.sort(start);
Arrays.sort(end);
//Compare the ends with each start to check if they would be able ot attend all meetings
for(int i=0;i<intervals.size()-1;i++){
if(end[i]>start[i+1]){return false;// should always be greater ethan or equal to
}
}
// if all cases pass then the user would be able to attend all the meeting
return true;
}
}
53) Meeting rooms II
/**
* Definition of Interval:
* public class Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* @param intervals: an array of meeting time intervals
* @return: the minimum number of conference rooms required
*/
public int minMeetingRooms(List<Interval> intervals) {
if (intervals.isEmpty()) return 0;
Collections.sort(
intervals,
(a, b) -> Integer.compare(a.start, b.start)
);
Queue<Interval> queue = new PriorityQueue<>((a, b) ->
Integer.compare(a.end, b.end)
);
int count = 0;
for (Interval interval : intervals) {
while (
!queue.isEmpty() && interval.start >= queue.peek().end
) queue.poll();
queue.offer(interval);
count = Math.max(count, queue.size());
}
return count;
}
}
// Two pointer approach
public class Solution {
public int minMeetingRooms(List<Interval> intervals) {
if (intervals.size() == 0) {
return 0;
}
int len = intervals.size();
int[] startTime = new int[len];
int[] endTime = new int[len];
for (int i = 0; i < len; i++) {
startTime[i] = intervals.get(i).start;
endTime[i] = intervals.get(i).end;
}
Arrays.sort(startTime);
Arrays.sort(endTime);
int res = 0;
int count = 0;
int s = 0;
int e = 0;
while (s < len) {
if (startTime[s] < endTime[e]) {
s++;
count++;
} else {
e++;
count--;
}
res = Math.max(res, count);
}
return res;
}
}
Longest common subsequence done using bottom up approach.
Pending: Didn't get 100% intuition in tabulation.
Do it using other approaches too. https://www.youtube.com/watch?v=I3Nc9ZWfgZE
Construct a binary tree form inorder and postorder traversal.
Easy but tricky, learn, code and practice different approaches
Tricky because you have got to know that the preorder range while making recursive calls are same as that of the mid range that we find out.
reference:
Longest palindromic substring done.
Pending : Different approach , DP
have confusion about the fact that if it doesn't store history of start and end then how are we getting the right answer
Palindromic substring done using the logic of iterating and checking for palindrome from the middle.
Pending: to implement it using DP and other approaches, revision of this logic
The idea here is to make a gap between two positions of the list and travel the list till the very end keeping the length/gap of the two positions/pointers the same and in the end when the pointer in the from reaches the end, the pointer behind it would be at a place that needs to be deleted so we perform linked list operations to skip one Node.
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (Objects.isNull(head) || Objects.isNull(head.next)) return null;
ListNode zeroIndexNode=new ListNode(0);
zeroIndexNode.next=head; //Joint 0 value node to the start of list
ListNode behind=zeroIndexNode;
ListNode front=zeroIndexNode;
while(n>0){
front=front.next;
n--;
} // create the distance equal to that of n
while(Objects.nonNull(front.next)){
front=front.next;
behind=behind.next;
}
behind.next=behind.next.next;
return zeroIndexNode.next;
}
}
In meeting rooms 2, first understand the code and then learn the code (Though the question seems easy the intuition is tricky to understand) then code it
Longest common subsequence done using bottom up approach.
Pending: Didn't get 100% intuition in tabulation.
Do it using other approaches too.
https://www.youtube.com/watch?v=I3Nc9ZWfgZE