Video

If higher[i] is true, it means starting from index i with an odd jump can eventually reach the end of the array, so we increment res.

Answer to Your Question: Why increment res only when higher[i] is true and not for lower[i]? The problem statement defines a "good" starting index as one from which you can reach the end by making some number of jumps. The first jump from any index is always an odd-numbered jump. Therefore, we are only interested in whether the odd jump (higher[i]) from that index can eventually lead to the end of the array. If higher[i] is true, it means starting at index i, you can reach the end by following the defined jumping rules. lower[i] being true is relevant only for subsequent jumps (even-numbered jumps), but it doesn't directly determine if i is a good starting index. If you were to increment res for lower[i], you would incorrectly count indices that can only be reached via even-numbered jumps but not as starting points themselves.

❤

Yeah it was great video

Thank you so much 😀

import java.util.*; class Solution { public int[] shortestDistanceAfterQueries(int n, int[][] queries) { // Create an adjacency list to represent the graph List<List<int[]>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } // Initially add the default roads for (int i = 0; i < n - 1; i++) { graph.get(i).add(new int[]{i + 1, 1}); // road to i+1 with weight 1 } // Result array to store shortest path lengths after each query int[] result = new int[queries.length]; // Process each query for (int i = 0; i < queries.length; i++) { int[] query = queries[i]; int u = query[0]; int v = query[1]; // Add the new road to the graph graph.get(u).add(new int[]{v, 1}); // road to v with weight 1 // Perform Dijkstra's algorithm to find the shortest path from city 0 to city n-1 result[i] = dijkstra(graph, n); } return result; } private int dijkstra(List<List<int[]>> graph, int n) { // Distance array to keep track of shortest distance from source int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[0] = 0; // Priority queue for Dijkstra's algorithm (min-heap) PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); pq.offer(new int[]{0, 0}); // {city, distance} while (!pq.isEmpty()) { int[] current = pq.poll(); int node = current[0]; int distance = current[1]; if (distance > dist[node]) continue; for (int[] neighbor : graph.get(node)) { int nextNode = neighbor[0]; int weight = neighbor[1]; if (dist[node] + weight < dist[nextNode]) { dist[nextNode] = dist[node] + weight; pq.offer(new int[]{nextNode, dist[nextNode]}); } } } // The shortest path to city n-1 return dist[n - 1] == Integer.MAX_VALUE ? -1 : dist[n - 1]; } }

@@expertfunda isnt it still giving tle??

@@expertfunda solve it using segment tree

/*I tried with wellman and dikshetra still getting problem, and I will fix and will provide the code */ import java.util.*; public class Solution { // Function to perform BFS and find shortest path from src to dest private int bfs(int src, int dest, Map<Integer, List<Integer>> graph, int n) { Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[n]; int[] distance = new int[n]; Arrays.fill(distance, -1); queue.offer(src); visited[src] = true; distance[src] = 0; while (!queue.isEmpty()) { int node = queue.poll(); if (node == dest) return distance[node]; for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); distance[neighbor] = distance[node] + 1; } } } return -1; // If no path is found } public int[] shortestDistanceAfterQueries(int n, int[][] queries) { // Initialize graph Map<Integer, List<Integer>> graph = new HashMap<>(); for (int i = 0; i < n; i++) { graph.put(i, new ArrayList<>()); } for (int i = 0; i < n - 1; i++) { graph.get(i).add(i + 1); } int[] result = new int[queries.length]; for (int i = 0; i < queries.length; i++) { // Add new road from queries[i][0] to queries[i][1] int u = queries[i][0]; int v = queries[i][1]; graph.get(u).add(v); // Compute shortest path from 0 to n - 1 result[i] = bfs(0, n - 1, graph, n); } return result; } }

yes, i will provide the fix

give

@@hawkop2386 import java.util.*; class Solution { public int[] shortestDistanceAfterQueries(int n, int[][] queries) { // Create an adjacency list to represent the graph List<List<int[]>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } // Initially add the default roads for (int i = 0; i < n - 1; i++) { graph.get(i).add(new int[]{i + 1, 1}); // road to i+1 with weight 1 } // Result array to store shortest path lengths after each query int[] result = new int[queries.length]; // Process each query for (int i = 0; i < queries.length; i++) { int[] query = queries[i]; int u = query[0]; int v = query[1]; // Add the new road to the graph graph.get(u).add(new int[]{v, 1}); // road to v with weight 1 // Perform Dijkstra's algorithm to find the shortest path from city 0 to city n-1 result[i] = dijkstra(graph, n); } return result; } private int dijkstra(List<List<int[]>> graph, int n) { // Distance array to keep track of shortest distance from source int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[0] = 0; // Priority queue for Dijkstra's algorithm (min-heap) PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); pq.offer(new int[]{0, 0}); // {city, distance} while (!pq.isEmpty()) { int[] current = pq.poll(); int node = current[0]; int distance = current[1]; if (distance > dist[node]) continue; for (int[] neighbor : graph.get(node)) { int nextNode = neighbor[0]; int weight = neighbor[1]; if (dist[node] + weight < dist[nextNode]) { dist[nextNode] = dist[node] + weight; pq.offer(new int[]{nextNode, dist[nextNode]}); } } } // The shortest path to city n-1 return dist[n - 1] == Integer.MAX_VALUE ? -1 : dist[n - 1]; } }

import java.util.HashMap; class Solution { public int[] shortestDistanceAfterQueries(int n, int[][] queries) { // Result array to store answers for each query int[] ans = new int[queries.length]; // Map to store the largest node reachable from a given node HashMap<Integer, Integer> map = new HashMap<>(); // Initialize the map to link each node to its immediate successor for (int i = 0; i < n - 1; i++) { map.put(i, i + 1); } // Process each query for (int i = 0; i < queries.length; i++) { int u = queries[i][0]; int v = queries[i][1]; // If u is not in the map or its range already includes v, the map size remains the same if (!map.containsKey(u) || map.get(u) >= v) { ans[i] = map.size(); continue; } // Remove all nodes between u and v (not including v) int end = map.get(u); while (end < v) { end = map.remove(end); } // Update the range for u map.put(u, v); // Store the result which is the current size of the map ans[i] = map.size(); } return ans; } }

import java.util.HashMap; class Solution { public int[] shortestDistanceAfterQueries(int n, int[][] queries) { // Result array to store answers for each query int[] ans = new int[queries.length]; // Map to store the largest node reachable from a given node HashMap<Integer, Integer> map = new HashMap<>(); // Initialize the map to link each node to its immediate successor for (int i = 0; i < n - 1; i++) { map.put(i, i + 1); } // Process each query for (int i = 0; i < queries.length; i++) { int u = queries[i][0]; int v = queries[i][1]; // If u is not in the map or its range already includes v, the map size remains the same if (!map.containsKey(u) || map.get(u) >= v) { ans[i] = map.size(); continue; } // Remove all nodes between u and v (not including v) int end = map.get(u); while (end < v) { end = map.remove(end); } // Update the range for u map.put(u, v); // Store the result which is the current size of the map ans[i] = map.size(); } return ans; } }

import java.util.HashMap; class Solution { public int[] shortestDistanceAfterQueries(int n, int[][] queries) { // Result array to store answers for each query int[] ans = new int[queries.length]; // Map to store the largest node reachable from a given node HashMap<Integer, Integer> map = new HashMap<>(); // Initialize the map to link each node to its immediate successor for (int i = 0; i < n - 1; i++) { map.put(i, i + 1); } // Process each query for (int i = 0; i < queries.length; i++) { int u = queries[i][0]; int v = queries[i][1]; // If u is not in the map or its range already includes v, the map size remains the same if (!map.containsKey(u) || map.get(u) >= v) { ans[i] = map.size(); continue; } // Remove all nodes between u and v (not including v) int end = map.get(u); while (end < v) { end = map.remove(end); } // Update the range for u map.put(u, v); // Store the result which is the current size of the map ans[i] = map.size(); } return ans; } }

Thanks I will do

Thank you! Cheers!

Problem Intuition: You are given an array where you can jump between indices following specific rules: On odd-numbered jumps, you must jump to a higher or equal value. On even-numbered jumps, you must jump to a lower or equal value. Your goal is to determine how many starting indices allow you to reach the end of the array by following these jumping rules. Example: Consider the array [10, 13, 12, 14, 15]. Starting from index 0, the first jump (odd) must go to a higher value. The smallest higher value after 10 is 12, found at index 2. From 12, you would attempt an even jump to a smaller value, but there isn’t any, so you get stuck. Starting from index 3, the first jump (odd) can go to the value 15, reaching the end of the array. Approach Intuition: 1. Backward Thinking: Start by thinking backward from the end of the array: If you start at the last index, you’re already at the end-so it's trivially a "good" index. For each previous index, determine if you can reach a "good" index by following the jumping rules. 2. Dynamic Decision Making: For each index i, you need to answer: Odd Jump: Can I jump to a higher value and eventually reach the end? Even Jump: Can I jump to a lower value and eventually reach the end? These questions are interdependent. If an odd jump from i reaches a "good" index that is itself reachable by an even jump, then i is a "good" index. 3. Efficient Calculation with TreeMap: To efficiently find the smallest/largest values you can jump to: Use a TreeMap to maintain a sorted order of values as you process the array. The ceilingEntry gives the smallest higher/equal value (for odd jumps). The floorEntry gives the largest lower/equal value (for even jumps). 4. Why Only Count Odd Jumps (higher[i])? The first jump from any index will always be an odd jump. If you can make a valid odd jump (higher[i]), you have a path to reach the end, so you count this index as "good." Even jumps (lower[i]) are crucial for decision-making but don’t determine if an index is "good" as a starting point.

I will try my best. Thank you bro

Thanks for letting me know I will update it

Problem Intuition: You are given an array where you can jump between indices following specific rules: On odd-numbered jumps, you must jump to a higher or equal value. On even-numbered jumps, you must jump to a lower or equal value. Your goal is to determine how many starting indices allow you to reach the end of the array by following these jumping rules. Example: Consider the array [10, 13, 12, 14, 15]. Starting from index 0, the first jump (odd) must go to a higher value. The smallest higher value after 10 is 12, found at index 2. From 12, you would attempt an even jump to a smaller value, but there isn’t any, so you get stuck. Starting from index 3, the first jump (odd) can go to the value 15, reaching the end of the array. Approach Intuition: 1. Backward Thinking: Start by thinking backward from the end of the array: If you start at the last index, you’re already at the end-so it's trivially a "good" index. For each previous index, determine if you can reach a "good" index by following the jumping rules. 2. Dynamic Decision Making: For each index i, you need to answer: Odd Jump: Can I jump to a higher value and eventually reach the end? Even Jump: Can I jump to a lower value and eventually reach the end? These questions are interdependent. If an odd jump from i reaches a "good" index that is itself reachable by an even jump, then i is a "good" index. 3. Efficient Calculation with TreeMap: To efficiently find the smallest/largest values you can jump to: Use a TreeMap to maintain a sorted order of values as you process the array. The ceilingEntry gives the smallest higher/equal value (for odd jumps). The floorEntry gives the largest lower/equal value (for even jumps). 4. Why Only Count Odd Jumps (higher[i])? The first jump from any index will always be an odd jump. If you can make a valid odd jump (higher[i]), you have a path to reach the end, so you count this index as "good." Even jumps (lower[i]) are crucial for decision-making but don’t determine if an index is "good" as a starting point.

thank u

Sure I’ll post link here Thank you

class Solution { public int superEggDrop(int k, int n) { // DP array to store the minimum attempts needed for i eggs and j floors int[][] dp = new int[k + 1][n + 1]; // Initialize base cases for (int i = 1; i <= k; i++) { dp[i][0] = 0; // 0 floors -> 0 attempts dp[i][1] = 1; // 1 floor -> 1 attempt } for (int j = 1; j <= n; j++) { dp[1][j] = j; // 1 egg -> j attempts for j floors } // Fill the DP table for (int i = 2; i <= k; i++) { for (int j = 2; j <= n; j++) { dp[i][j] = Integer.MAX_VALUE; for (int x = 1; x <= j; x++) { int broken = dp[i - 1][x - 1]; // Egg breaks int notBroken = dp[i][j - x]; // Egg doesn't break int worst = 1 + Math.max(broken, notBroken); dp[i][j] = Math.min(dp[i][j], worst); } } } // The result is in dp[k][n] return dp[k][n]; } }

Welcome 🤓

Thanks for liking

Could you please share me link and I will go thru exact question ? Thank you :)

czcams.com/video/3CdeZNpiS6Q/video.html

We have to take max value from completing each operations result. We are storing in list and then will get top element to find the score. Thanks

Thank you Leon

Thank you sure will take care of this

Thanks

Thank you for asking today I will upload and ping you to watch. Thanks for reminding me

@Priyanshu please watch czcams.com/video/oIGSvc_qfIU/video.html

Yes road[2] is distance Thanks

Yes Akshay bilkul sahi kaha I forgot

Sure, I will

The time complexity of this solution is O(m * (r - l + 1)), where m is the number of queries and (r - l + 1) is the length of each query range. In the outer loop, we iterate m times over the queries array. In the inner loop, we iterate (r - l + 1) times over the words array for each query, where r and l are the right and left indices of the query range, respectively. Therefore, the total time complexity is O(m * (r - l + 1)). thank you

accepted code is here czcams.com/video/JeHkfrbdCNA/video.html thank you

class Solution { public int[] vowelStrings(String[] words, int[][] queries) { int n = words.length; int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { dp[i] = dp[i - 1]; String word = words[i - 1]; if (isVowel(word.charAt(0)) && isVowel(word.charAt(word.length() - 1))) { dp[i]++; } } int[] ans = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int li = queries[i][0]; int ri = queries[i][1]; ans[i] = dp[ri + 1] - dp[li]; } return ans; } private boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } }

Thanks

Yes, there can be optimized way. Please suggest if you think there can be another approach. Also like share and subscribe for more videos

means b[k]-a[k] is not working in cpp but a[k]>b[k] is working ,why??please sir reply

@@nikhilrajsoni4541 In C++, you can use the sort() function from the algorithm library to sort the students by their scores in the kth exam. Here's an example of how you can sort a matrix score by the scores in the kth exam: sort(score.begin(), score.end(), [](const vector<int>& a, const vector<int>& b) { return a[k] > b[k]; }); Actually, Java has inbuild class Comparator and you have to override according to need.

@@expertfunda got you ,Thank you soo much I was so confused for many years

We have to override the compare method of comparator Like @Override public int compare(int a, int b) {} thanks

In C++, you can use the sort() function from the algorithm library to sort the students by their scores in the kth exam. Here's an example of how you can sort a matrix score by the scores in the kth exam: sort(score.begin(), score.end(), [](const vector<int>& a, const vector<int>& b) { return a[k] > b[k]; });

My pleasure 😊

Yeah, Let me update the same. Thank you Kena Dave :)