vaibhav joshi’s Post

🎯 LeetCode Daily Challenge - Day 9 Dec 2024 🚀 Today’s problem: "3152. Special Array II" 🔄✨ 💡 The Problem: An array is considered special if every pair of its adjacent elements contains two numbers with different parity. You are given an array of integer nums and a 2D integer matrix queries, where for queries[i] = [fromi, toi] your task is to check that  subarray  nums[fromi..toi] is special or not.Return an array of booleans answer such that answer[i] is true if nums[fromi..toi] is special.   Example 1: Input: nums = [3,4,1,2,6], queries = [[0,4]] Output: [false] Explanation: The subarray is [3,4,1,2,6]. 2 and 6 are both even. 🛠️ Approach Step 1: Build the Prefix Array We use a prefix array to count special pairs as we move through nums: If two consecutive numbers have the same "team" (both 🟢 or both 🔴), we increase the count. Otherwise, the count stays the same. For example, in [4, 3, 1, 6]: At index 0: No pairs yet → prefix[0] = 0. At index 1: (4, 3) isn’t special → prefix[1] = 0. At index 2: (3, 1) is special → prefix[2] = 1. At index 3: (1, 6) isn’t special → prefix[3] = 1. Final prefix array: [0, 0, 1, 1]. Step 2: Process Queries For each query [left, right]: Calculate the number of special pairs in the range using the prefix array: specialCount = prefix[right] - (left > 0 ? prefix[left - 1] : 0); Time Complexity: Building the prefix array: O(n) (where n is the size of nums). Answering queries: O(q) (where q is the number of queries). Total: O(n + q). Space Complexity: Storing the prefix array: O(n). Total: O(n).

𝗗𝗮𝘆 41𝗼𝗳 #𝟭𝟬𝟬𝗱𝗮𝘆𝘀𝗼𝗳𝗰𝗼𝗱𝗲 LeetCode daily challenge 🚀 Problem --> 𝟓𝟒𝟑. 𝐃𝐢𝐚𝐦𝐞𝐭𝐞𝐫 𝐨𝐟 𝐁𝐢𝐧𝐚𝐫𝐲 𝐓𝐫𝐞𝐞 🔽🔽 Explanation 🔽🔽 𝟭. 𝗜𝗻𝗶𝘁𝗶𝗮𝗹𝗶𝘇𝗮𝘁𝗶𝗼𝗻 𝗼𝗳 𝗺𝗮𝘅 𝗩𝗮𝗿𝗶𝗮𝗯𝗹𝗲: --> We begin by initializing a variable max outside of any method. This variable is crucial as it keeps track of the maximum diameter encountered during the traversal of the binary tree. --> By initializing it to 0, we ensure that it starts with the smallest possible value and gets updated as we traverse the tree. 𝟮. 𝗘𝗻𝘁𝗿𝘆 𝗣𝗼𝗶𝗻𝘁 𝗳𝗼𝗿 𝗗𝗶𝗮𝗺𝗲𝘁𝗲𝗿 𝗖𝗮𝗹𝗰𝘂𝗹𝗮𝘁𝗶𝗼𝗻: --> The diameterOfBinaryTree method serves as the entry point for calculating the diameter of the binary tree. --> It takes the root of the binary tree as input and calls the maxDepth method to compute the depth of each node and update the max variable accordingly. 𝟯. 𝗥𝗲𝗰𝘂𝗿𝘀𝗶𝘃𝗲 𝗗𝗲𝗽𝘁𝗵 𝗖𝗮𝗹𝗰𝘂𝗹𝗮𝘁𝗶𝗼𝗻: --> The maxDepth method is responsible for recursively calculating the maximum depth of each subtree rooted at the current node. --> It follows a depth-first traversal approach, recursively visiting each node in the tree until it reaches the leaf nodes. --> At each node, it computes the maximum depth of its left and right subtrees by recursively calling maxDepth. 𝟰. 𝗨𝗽𝗱𝗮𝘁𝗶𝗻𝗴 𝗠𝗮𝘅𝗶𝗺𝘂𝗺 𝗗𝗶𝗮𝗺𝗲𝘁𝗲𝗿: --> As the maxDepth method traverses each node in the binary tree, it calculates the depths of the left and right subtrees. --> At each node, it computes the sum of the depths of the left and right subtrees and updates the max diameter if this sum exceeds the current maximum diameter. --> This step ensures that we keep track of the longest path encountered so far, which represents the diameter of the binary tree. 𝟱. 𝗥𝗲𝘁𝘂𝗿𝗻𝗶𝗻𝗴 𝗠𝗮𝘅𝗶𝗺𝘂𝗺 𝗗𝗲𝗽𝘁𝗵: --> Finally, the maxDepth method returns the maximum depth of the current node by adding 1 to the maximum depth of its subtrees. --> This incremental addition ensures that the depth value returned for each node represents the path length from that node to the farthest leaf node. --> By returning the maximum depth, we facilitate the diameter calculation process, as it enables us to compute the sum of depths of left and right subtrees at each node. 𝗪𝗿𝗮𝗽𝗽𝗶𝗻𝗴 𝘂𝗽 𝗺𝘆 𝘁𝗼𝗱𝗮𝘆'𝘀 𝗰𝗼𝗱𝗶𝗻𝗴 𝗷𝗼𝘂𝗿𝗻𝗲𝘆 𝘂𝗽𝗱𝗮𝘁𝗲! 💻 𝗜𝗳 𝘆𝗼𝘂 𝗵𝗮𝘃𝗲 𝗮𝗻𝘆 𝗾𝘂𝗲𝘀𝘁𝗶𝗼𝗻𝘀 𝗼𝗿 𝗶𝗻𝘀𝗶𝗴𝗵𝘁𝘀 𝘁𝗼 𝘀𝗵𝗮𝗿𝗲, 𝗳𝗲𝗲𝗹 𝗳𝗿𝗲𝗲 𝘁𝗼 𝗿𝗲𝗮𝗰𝗵 𝗼𝘂𝘁. 𝗟𝗲𝘁'𝘀 𝗰𝗼𝗱𝗲 𝘁𝗼𝗴𝗲𝘁𝗵𝗲𝗿! 🚀 #programmingtips #AlgorithmExplained #codingjourney #CodeBreakdown #codingchallenge #javaprogramming #LeetCodeSolution #datastructures #techupdates #100daysofcode #codingcommunity #problemsolving #DailyCodingChallenge #CodeWithExplanation #softwareengineering #learntocode #codereview #CodingInspiration #developercommunity #programminglife #CodeShare #codingprogress #techlearning #CodeCommitment #CodeInJava #codingskills #CodeExplained

🚀 Day 36/100 of #100DaysOfLeetCode Challenge Today I solved the leetCode problem 😀 Problem: #Sort_Even_and_Odd_Indices_Independently 📌Problem Number: 2164 🕰 Time Complexity: O( n logn) 🌌Space Complexity: O( n ) 📊Difficulty: Easy 💡Problem Description: You are given a 0-indexed integer array nums. Rearrange the values of nums according to the following rules: Sort the values at odd indices of nums in non-increasing order. For example, if nums = [4,1,2,3] before this step, it becomes [4,3,2,1] after. The values at odd indices 1 and 3 are sorted in non-increasing order. Sort the values at even indices of nums in non-decreasing order. For example, if nums = [4,1,2,3] before this step, it becomes [2,1,4,3] after. The values at even indices 0 and 2 are sorted in non-decreasing order. Return the array formed after rearranging the values of nums.   Example 1: Input: nums = [4,1,2,3] Output: [2,3,4,1] Explanation: First, we sort the values present at odd indices (1 and 3) in non-increasing order. So, nums changes from [4,1,2,3] to [4,3,2,1]. Next, we sort the values present at even indices (0 and 2) in non-decreasing order. So, nums changes from [4,1,2,3] to [2,3,4,1]. Thus, the array formed after rearranging the values is [2,3,4,1]. Example 2: Input: nums = [2,1] Output: [2,1] Explanation: Since there is exactly one odd index and one even index, no rearrangement of values takes place. The resultant array formed is [2,1], which is the same as the initial array. ➡Code: class Solution(object):     def sortEvenOdd(self, nums):                 arr_odd=[]         arr_even=[]         arr=[]         for i in range(len(nums)):             if i%2==0:                 arr_even.append(nums[i])             else:                 arr_odd.append(nums[i])         arr_odd.sort(reverse=True)         arr_even.sort()         odd=0         even=0         for i in range(len(nums)):             if i% 2==0:                 arr.append(arr_even[even])                 even+=1             else:                 arr.append(arr_odd[odd])                 odd+=1         return arr 🔗Problem link : https://lnkd.in/dnECCT-Z Let’s keep leveling up our coding skills*! 💪 #CodingChallenge #LeetCode #ProblemSolving #Dsa #KeepLearning #AlgorithmicThinking #KeepGrowing #CodingIsFun

𝗗𝗮𝘆 84 𝗼𝗳 #𝟭𝟬𝟬𝗱𝗮𝘆𝘀𝗼𝗳𝗰𝗼𝗱𝗲 LeetCode daily challenge 🚀 Problem --> 𝟏𝟗𝟕𝟏. 𝐅𝐢𝐧𝐝 𝐢𝐟 𝐏𝐚𝐭𝐡 𝐄𝐱𝐢𝐬𝐭𝐬 𝐢𝐧 𝐆𝐫𝐚𝐩𝐡 🔽🔽 Explanation 🔽🔽 𝟭. 𝗨𝗻𝗶𝗼𝗻𝗙𝗶𝗻𝗱 𝗖𝗹𝗮𝘀𝘀: --> This class encapsulates the Union-Find data structure. --> The constructor initializes arrays id and rank, essential components of Union-Find. --> Each element in id signifies its parent, initially set to itself, establishing disjoint sets. --> rank stores the rank of each element, pivotal for optimizing union operations. class UnionFind {  public UnionFind(int n) {   id = new int[n];   rank = new int[n];   for (int i = 0; i < n; ++i)    id[i] = i;  } 𝟮. 𝘂𝗻𝗶𝗼𝗻𝗕𝘆𝗥𝗮𝗻𝗸 𝗠𝗲𝘁𝗵𝗼𝗱: --> unionByRank method executes the union operation employing the rank-based optimization strategy. --> It retrieves the roots of elements u and v using the find method. --> If both elements already belong to the same set, no further action is needed. --> Otherwise, it merges the smaller rank tree into the larger one. In case of tie, the rank of the resulting tree increases.  public void unionByRank(int u, int v) {  ........   }  } 𝟯. 𝗳𝗶𝗻𝗱 𝗠𝗲𝘁𝗵𝗼𝗱: --> find method recursively traverses the parent pointers to determine the root of an element. --> It employs path compression, optimizing subsequent find operations by updating each traversed node's parent to the root.  public int find(int u) {   return id[u] == u ? u : (id[u] = find(id[u]));  } 𝟰. 𝗥𝗲𝗳𝗲𝗿𝗲𝗻𝗰𝗲 𝗩𝗮𝗿𝗶𝗮𝗯𝗹𝗲𝘀 𝗜𝗻𝗶𝘁𝗶𝗮𝗹𝗶𝘇𝗮𝘁𝗶𝗼𝗻: Private member variables id and rank store parent pointers and ranks respectively, crucial for Union-Find operations.  private int[] id;  private int[] rank; } 𝟱. 𝗦𝗼𝗹𝘂𝘁𝗶𝗼𝗻 𝗖𝗹𝗮𝘀𝘀: --> The Solution class furnishes a method validPath to ascertain the existence of a path between source and destination, given the edges. --> It initializes a Union-Find instance uf with n elements, laying the groundwork for connectivity analysis. --> Subsequently, it performs union operations for each edge, consolidating connected components. --> Finally, it validates if both source and destination belong to the same set, employing the find method, and returns the verdict. 𝗪𝗿𝗮𝗽𝗽𝗶𝗻𝗴 𝘂𝗽 𝗺𝘆 𝘁𝗼𝗱𝗮𝘆'𝘀 𝗰𝗼𝗱𝗶𝗻𝗴 𝗷𝗼𝘂𝗿𝗻𝗲𝘆 𝘂𝗽𝗱𝗮𝘁𝗲! 💻 𝗜𝗳 𝘆𝗼𝘂 𝗵𝗮𝘃𝗲 𝗮𝗻𝘆 𝗾𝘂𝗲𝘀𝘁𝗶𝗼𝗻𝘀 𝗼𝗿 𝗶𝗻𝘀𝗶𝗴𝗵𝘁𝘀 𝘁𝗼 𝘀𝗵𝗮𝗿𝗲, 𝗳𝗲𝗲𝗹 𝗳𝗿𝗲𝗲 𝘁𝗼 𝗿𝗲𝗮𝗰𝗵 𝗼𝘂𝘁. 𝗟𝗲𝘁'𝘀 𝗰𝗼𝗱𝗲 𝘁𝗼𝗴𝗲𝘁𝗵𝗲𝗿! 🚀 #programmingtips #AlgorithmExplained #codingjourney #CodeBreakdown #codingchallenge #javaprogramming #LeetCodeSolution #datastructures #techupdates #100daysofcode #codingcommunity #problemsolving #DailyCodingChallenge #CodeWithExplanation #softwareengineering #learntocode #codereview #CodingInspiration #developercommunity #programminglife #CodeShare #codingprogress #techlearning #CodeCommitment #CodeInJava #codingskills #CodeExplained 𝟭. 𝗨𝗻𝗶𝗼𝗻𝗙𝗶𝗻𝗱 𝗖𝗹𝗮𝘀𝘀:

🚀 Day 39 of #100DaysOfCode 🚀 LeetCode 2191. Sort the Jumbled Numbers You are given a 0-indexed integer array mapping which represents the mapping rule of a shuffled decimal system. mapping[i] = j means digit i should be mapped to digit j in this system. The mapped value of an integer is the new integer obtained by replacing each occurrence of digit i in the integer with mapping[i] for all 0 <= i <= 9. You are also given another integer array nums. Return the array nums sorted in non-decreasing order based on the mapped values of its elements. Notes: Elements with the same mapped values should appear in the same relative order as in the input. The elements of nums should only be sorted based on their mapped values and not be replaced by them.   Example 1: Input: mapping = [8,9,4,0,2,1,3,5,7,6], nums = [991,338,38] Output: [338,38,991] Explanation: Map the number 991 as follows: 1. mapping[9] = 6, so all occurrences of the digit 9 will become 6. 2. mapping[1] = 9, so all occurrences of the digit 1 will become 9. Therefore, the mapped value of 991 is 669. 338 maps to 007, or 7 after removing the leading zeros. 38 maps to 07, which is also 7 after removing leading zeros. Since 338 and 38 share the same mapped value, they should remain in the same relative order, so 338 comes before 38. Thus, the sorted array is [338,38,991]. Example 2: Input: mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123] Output: [123,456,789] Explanation: 789 maps to 789, 456 maps to 456, and 123 maps to 123. Thus, the sorted array is [123,456,789].

#LeetCode Challenge Day4:Problem 2 🚀Algorithm Spotlit : Solving Problem On Valid Parentheses 🔍 Approach Using a Stack: The solution employs a stack (st) to keep track of the opening brackets as they appear in the string s. The stack is a Last-In-First-Out (LIFO) data structure, making it ideal for this type of matching problem where you need to ensure that the most recent opening bracket matches the next closing brackets. The code iterates over each character in the string s using a range-based for loop. If the character is an opening bracket ('{', '(', or '['), it is pushed onto the stack. If the character is a closing bracket ('}', ')', or ']'), the code first checks if the stack is empty. If the stack is empty, it means there is no matching opening bracket for this closing bracket, so the function returns false. If the stack is not empty, the code pops the top element from the stack and checks if it matches the current closing bracket. If the popped element matches the expected opening bracket for the current closing bracket, the loop continues. If it does not match, the function returns false. After processing all characters in the string, the code checks if the stack is empty. If the stack is empty, it means all opening brackets had matching closing brackets, so the function returns true. If the stack is not empty, it means there are unmatched opening brackets left, so the function returns false.

Hello Connections, 100 days of Leetcode challenge: Day 22: Subsets. Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. Approach:The code generates all subsets of an array using backtracking. It maintains a global list `Ans` to store subsets. It initializes an empty list `op` for each subset and iterates through the array. At each index, it makes two choices: include or exclude the current element. After processing each index, it backtracks by removing the last element added to `op`. When all elements are processed, the current subset is added to `Ans`. This process continues recursively until all indices are covered. Finally, it returns the list of all subsets. Method to Solve: There are tooo many approach is available but this code sloved by using "Back-Tracking" #100DaysofLeetcodeChallenge

Solved 4/4 in today's LeetCode Weekly Contest 398 ! Here is the detailed editorial by my side... 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝟏& 𝟐: For every index i you will store the last index j such that subarray (i,j) is special. Start iterating from back , if (nums[i]%2 != nums[i+1]%2) then ans[i] will be ans[i+1] else it will be 'i'. Now for every query {from,to} if ans[from] >=to then subarray(from,to) is special else not. For problem 1 just check if ans[0]==n-1. 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝟑: Values can be from 0 to 9. Suppose length of each integer is k. Then we will have a 2D array 'temp' of size k*10. Where temp[i][j] will tell us total number of value 'j' present at position 'i' of all the integers when converted to string. Now we will iterate over all the integers and for each integer 'p' ,initially 'i' will be 0. We will increment temp[i++][p%10] by 1 and divide p by 10 while it is greater than 0. Now once we are done with all the integers , finally for each position we want total number of distinct pairs . So we will iterate over each position 'i' and then for every pair (j,k) where j!=k we will add temp[i][j]*temp[i][k] in our answer [ Inner loop for j(0 to 9) and for k(j+1,9) ]. 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝟒: DP + Hashing As k can be upto 1e9 we cannot memoize our solution with standard DP as the size would be too large. First let's understand the states of dp : 𝐒𝐭𝐚𝐭𝐞𝐬 : [i][jump][movedown or not] [i][jump][1] -> number of ways to reach stair k if I start from stair 'i' and current jump value is 'jump' and I can move down one step if required. [i][jump][0] -> number of ways to reach stair k if I start from stair 'i' and current jump value is 'jump' and I cannot move down one step from here. 𝐒𝐭𝐚𝐭𝐞 𝐓𝐫𝐚𝐧𝐬𝐢𝐭𝐢𝐨𝐧: {i,j,k} // Base case if(i>target+1) return 0; // Move down one step from current stair If (i>0 && k==true) then state(i,j,k) = state(i,j,k) + state(i-1,j,!k); // Move up 2^j steps from current stair state(i,j,k) = state(i,j,k) + state(i+pow(2,j),j+1,k); return state(i,j,k) + (1 if i==target); 𝐇𝐨𝐰 𝐭𝐨 𝐦𝐞𝐦𝐨𝐢𝐳𝐞 𝐢𝐭 𝐧𝐨𝐰 ? Have an unordered_map of type <string,int> . Now state (i,j,k) can be represented in form of string like "i--j--k". This string will be unique so we can memoize our solution now. state(i,j,k){ 1) base case 2) string s = to_string(i) + "--" + to_string(j) + "--" + (k ? "1" : "0"); if(mp.find(s) != mp.end()) return mp[s]; 3) Add answer for next states. 4) return mp[s] = answer; } That's it from my side 💙 Ps: Misread 3rd problem so got 2 penalties 😥 #leetcode #weeklycontest398 #leetcodecontest #leetcode2023 #codingjourney #codingcommunity #weeklycontest #competitiveprogramming #codingchallenge #cppprogramming #cpp #gfg #codechef #codeforces #contest #approach #solution #intuition #achievement #placementpreparation #placements #improvement #solutions #leetcodeweeklycontest #achievementunlocked #goals #competitivecoding #cprogramming #datastructuresandalgorithms #datastructures #algorithms

Let's solve today's problem of the day on leetcode. Problem statement: You are given a 0-indexed m x n matrix grid consisting of positive integers. You can start at any cell in the first column of the matrix, and traverse the grid in the following way: From a cell (row, col), you can move to any of the cells: (row - 1, col + 1), (row, col + 1) and (row + 1, col + 1) such that the value of the cell you move to, should be strictly bigger than the value of the current cell. Return the maximum number of moves that you can perform. My Approach: Basically, When i faced with the challenge of navigating a grid from the leftmost to the rightmost column, my first instinct was to explore every possible path. I thought, Why not check all the ways I can move and find the path that takes the most moves? I started with a Depth-First Search (DFS) to traverse all possible routes. It was a solid approach, but I soon got a hiccup TLE (time limit exceeded ) errors in some test cases! 😅 To tackle this, I turned to dynamic programming (DP) and introduced memoization. This allowed me to record results and avoid redundant calculations, significantly speeding things up. code: class Solution { public:  int dfs(vector<vector<int>>& grid, int row, int col, vector<vector<int>>&dp) {         if (col == grid[0].size() - 1) return 0;                 if (dp[row][col] != -1) return dp[row][col];                 int maxi = 0;         vector<pair<int, int>> directions = {{-1, 1}, {0, 1}, {1, 1}};                 for (auto it : directions) {             int newR = row + it.first, newC = col + it.second;             if (newR >= 0 && newR < grid.size() && newC < grid[0].size() && grid[newR][newC] > grid[row][col]) {                 maxi = max(maxi, 1 + dfs(grid, newR, newC, dp));             }         }                 return dp[row][col] = maxi;     }     int maxMoves(vector<vector<int>>& grid) {         int m = grid.size(), n = grid[0].size();         vector<vector<int>> dp(m, vector<int>(n, -1));         int maxi = 0; for (int i = 0; i < m; i++) {             maxi= max(maxi, dfs(grid, i, 0, dp));         } return maxi;     } };

🌟 Just tackled another problem on LeetCode! 🚀 🧠 Problem: 2392. Build a Matrix With Conditions 🔗 Problem Link: https://lnkd.in/dRAGcnVi 📌 Difficulty: Hard 🎓 Topics: Array, Graph, Topological Sort, Matrix 🏢 Companies: Various You are given a positive integer k. You are also given: A 2D integer array rowConditions of size n where rowConditions[i] = [abovei, belowi], and A 2D integer array colConditions of size m where colConditions[i] = [lefti, righti]. The two arrays contain integers from 1 to k. You have to build a k x k matrix that contains each of the numbers from 1 to k exactly once. The remaining cells should have the value 0. The matrix should also satisfy the following conditions: The number abovei should appear in a row that is strictly above the row at which the number belowi appears for all i from 0 to n - 1. The number lefti should appear in a column that is strictly left of the column at which the number righti appears for all i from 0 to m - 1. 🚀 Example 1: Input: k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]] Output: [[3,0,0],[0,0,1],[0,2,0]] Explanation: The row conditions are: 1 is above 2, and 3 is above 2. The column conditions are: 2 is left of 1, and 3 is left of 2. The resulting matrix is valid as it satisfies all conditions. 🚀 Example 2: Input: k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]] Output: [] Explanation: The conditions contradict each other, hence no valid matrix can be constructed. 💡 Constraints: 2 <= k <= 400 1 <= rowConditions.length, colConditions.length <= 104 rowConditions[i].length == colConditions[i].length == 2 1 <= abovei, belowi, lefti, righti <= k abovei != belowi lefti != righti Happy Coding! 💪🎉 #LeetCode #Programming #Algorithm #Matrix #CodeChallenge #DailyCoding #Java #DataStructure #DeveloperLife #CodeWithMe #Chitkara