Nitin Singh’s Post

🚀 DSA Progress – Day 112 ✅ Problem #560: Subarray Sum Equals K 🧠 Difficulty: Medium | Topics: Array, Prefix Sum, Hash Map 🔍 Approach: Implemented the Prefix Sum + Hash Map technique to efficiently count subarrays whose sum equals k. Step 1 (Prefix Sum): Maintain a running sum (prefix_sum) as we iterate through the array. Step 2 (Check for Required Sum): For each prefix_sum, check if (prefix_sum - k) exists in the hashmap. If yes → it means a subarray ending at the current index sums to k. Step 3 (Store Frequency): Use a dictionary (mp) to store how many times each prefix sum has appeared. This allows counting multiple subarrays efficiently. 🕒 Time Complexity: O(n) 💾 Space Complexity: O(n) (for hashmap storage) 📁 File: https://lnkd.in/g7acMKiA 📚 Repo: https://lnkd.in/g8Cn-EwH 💡 Learned: This problem strengthened my understanding of how prefix sums can simplify subarray-related questions. Instead of manually checking every subarray, we convert the problem into recognizing a pattern using previous sums. This is a powerful technique that shows up frequently in interview-level array problems. ✅ Day 112 complete — counted hidden subarrays like a pro! 🔢🎯✨ #LeetCode #DSA #Python #Arrays #PrefixSum #HashMap #Algorithm #DailyCoding #InterviewPrep #GitHubJourney #ProblemSolving

🚀 DSA Challenge – Day 90 Problem: Single Element in a Sorted Array ⚙️🔍 This problem was a clever application of binary search where understanding the index patterns of paired elements was the key to achieving logarithmic efficiency. 🧠 Problem Summary: You are given a sorted array where every element appears exactly twice, except for one element that appears only once. Your task: return that single element in O(log n) time and O(1) space. ⚙️ My Approach: 1️⃣ Used binary search to narrow down the segment containing the single element. 2️⃣ Checked if the middle element breaks the pairing rule — if so, that’s our unique number. 3️⃣ Observed the pattern: Before the single element, pairs start at even indices. After it, pairs start at odd indices. 4️⃣ Used this parity observation to adjust the search boundaries efficiently. 📈 Complexity: Time: O(log n) → Binary search halves the search space each step. Space: O(1) → Constant space used. ✨ Key Takeaway: Sometimes, the structure of sorted pairs reveals more than meets the eye — a small parity trick transforms a linear scan into a logarithmic search. ⚡ 🔖 #DSA #100DaysOfCode #LeetCode #ProblemSolving #BinarySearch #Algorithms #CodingChallenge #Python #Optimization #EfficientCode #TechCommunity #InterviewPrep #LearningByBuilding #CodeEveryday

🚀 DSA Challenge – Day 80 Problem: Maximum Distance Between Valid Pairs 🌊📏 Today’s problem tested the combination of binary search and array monotonicity — finding the farthest valid pair between two non-increasing arrays! 🧠 Problem Summary: We’re given two non-increasing arrays, nums1 and nums2. A pair (i, j) is valid if: i ≤ j, and nums1[i] ≤ nums2[j]. The goal is to find the maximum distance (j - i) among all valid pairs. ⚙️ My Approach: 1️⃣ Iterate through each element in nums1. 2️⃣ Use binary search on nums2 to find the farthest valid index satisfying the condition. 3️⃣ Keep track of the maximum j - i distance encountered. This solution leverages the sorted (non-increasing) property of arrays for logarithmic efficiency. 📈 Complexity: Time: O(n log m) → For each element in nums1, a binary search on nums2. Space: O(1) → Only a few variables used. ✨ Key Takeaway: Sometimes, monotonic properties allow you to blend binary search with iteration — turning what looks like a brute-force problem into a clean and efficient search-based solution. ⚡ 🔖 #DSA #100DaysOfCode #LeetCode #ProblemSolving #Algorithms #BinarySearch #TwoPointers #CodingChallenge #Python #InterviewPrep #TechCommunity #Optimization #EfficientCode #CodeEveryday

🚀 Solving Binary Subarray With Sum — From Brute Force to Optimal I recently solved LeetCode 930: Binary Subarray With Sum, and it turned out to be a great learning path across multiple techniques 💡 Problem: Count subarrays in a binary array whose sum equals a target (goal). My approach evolution: 1️⃣ Brute Force (O(n²)) – Check all (i, j) pairs. 2️⃣ Prefix Sum Array – Simplified sum calculation but still O(n²). 3️⃣ Prefix Sum + HashMap (O(n)) – Store prefix frequencies to count valid subarrays efficiently. 4️⃣ Sliding Window – For binary arrays, maintain subarray sum dynamically. 5️⃣ Special Case (goal == 0) – Count zero stretches combinatorially: k * (k + 1) / 2. ✅ Final solution combines: Prefix Sum Frequency (for goal > 0) Zero Stretch Counting (for goal = 0) Key takeaway: From brute force to optimized O(n), this problem teaches how prefix sums, hash maps, and combinatorics work together for elegant problem-solving. #LeetCode #ProblemSolving #DataStructures #Algorithms #CodingJourney #PrefixSum #SlidingWindow #Python

🚀 DSA Challenge – Day 84 Problem: Reachable Nodes in a Restricted Tree 🌲🚫 This problem was a perfect blend of graph traversal and constraint handling, where we must carefully explore a tree while avoiding restricted nodes. 🧠 Problem Summary: You are given a tree with n nodes (0-indexed) and a list of edges that describe the connections between them. Some nodes are restricted, meaning you cannot visit or pass through them. Starting from node 0, the goal is to determine how many nodes are reachable without visiting any restricted ones. ⚙️ My Approach: 1️⃣ Build an adjacency list representation of the tree. 2️⃣ Store all restricted nodes in a set for quick lookup. 3️⃣ Use Depth-First Search (DFS) to traverse the graph, skipping restricted or already visited nodes. 4️⃣ Accumulate a count of all valid reachable nodes. 📈 Complexity: Time: O(n) → Each node and edge is processed once. Space: O(n) → For adjacency list, recursion stack, and visited set. ✨ Key Takeaway: Even simple DFS problems become interesting when constraints are introduced. Efficient use of sets and recursion can elegantly handle conditions like restricted traversal in trees or graphs. 🌿 🔖 #DSA #100DaysOfCode #LeetCode #GraphTheory #TreeTraversal #DFS #Python #ProblemSolving #CodingChallenge #InterviewPrep #Algorithms #EfficientCode #TechCommunity #CodeEveryday #LearningByBuilding

🚀 LeetCode #1625: Lexicographically Smallest String After Applying Operations Today’s problem was about transforming a numeric string using two operations: adding a value to digits at odd indices and rotating the string, to get the lexicographically smallest result possible. The challenge was to handle infinite possibilities smartly. I used a Breadth First Search (BFS) approach to systematically explore all reachable string states while keeping track of visited ones. 💡 Key Takeaways: - Some problems don’t need a direct formula, they need systematic exploration. - BFS is not just for graphs; it’s a powerful tool for exploring state transitions too. - Modular arithmetic and rotation logic often come together in string manipulation problems. This one was a great reminder that clean logic and state tracking can solve even the most “infinite looking” problems efficiently. #LeetCode #ProblemSolving #Python #DSA #CodingChallenge #Algorithms #BFS #StringManipulation #LearningEveryday

Day 57: Binary Tree Zigzag Level Order Traversal 🎢 I'm continuing my journey with an advanced tree traversal problem on Day 57 of #100DaysOfCode: "Binary Tree Zigzag Level Order Traversal." The challenge is to return the nodes of a binary tree level by level, alternating the direction of traversal (left-to-right, then right-to-left, and so on). My solution builds upon the standard Breadth-First Search (BFS) algorithm, using a queue (deque): Level Traversal: I process the tree level by level, finding the level_size in each iteration. Direction Toggle: I use a boolean flag (left_to_right) to track the current direction. Zigzag Logic: Inside the level loop, I use a simple conditional: if left_to_right is true, I append the node value normally. If it's false, I insert the node value at the beginning of the current level's list (current_level.insert(0, node.val)). Optimal Flip: After processing the entire level, I flip the left_to_right flag (left_to_right = not left_to_right) for the next level. This single-pass BFS approach ensures all nodes are visited exactly once, achieving an optimal O(n) time complexity and O(n) space complexity. My solution was accepted with 100% runtime efficiency! #Python #DSA #Algorithms #Trees #BFS #100DaysOfCode #ProblemSolving #Zigzag

Day 62: Recover Binary Search Tree (BST) 🌳 I'm continuing my journey on Day 62 of #100DaysOfCode with a challenging BST problem: "Recover Binary Search Tree." The task is to fix a BST where exactly two nodes have been swapped by mistake, all without changing the tree's structure. The key insight relies on the property of Inorder Traversal of a BST, which always yields nodes in ascending order. Inorder Traversal: I first perform a standard inorder traversal (using recursion) to store the node values in an ascending list (inorder). Finding Swapped Nodes: I then iterate through the inorder list to find the two misplaced nodes. A violation occurs when inorder[i-1] > inorder[i]. The first misplaced node (first) is the larger element of the first violation. The second misplaced node (second) is the smaller element of the last violation. Correction: Finally, I swap the values of the two nodes found in the original tree. This method achieves an O(n) time complexity and O(n) space complexity (due to storing the inorder array). My solution was accepted with 100% runtime efficiency! #Python #DSA #Algorithms #BST #InorderTraversal #100DaysOfCode #ProblemSolving

📊 Experiment 11 – Decision Tree Classifier In this experiment, I got hands-on with the Decision Tree Classifier, a model that works just like how we make decisions in real life — step by step! 🌿 I learned how the algorithm splits data based on important features and how each branch leads to a clear outcome. Building and visualizing the tree helped me understand how models make logical decisions and how pruning helps prevent overfitting. 📁 GitHub: https://lnkd.in/eTtC53qu 🎓 Guided by: Ashish Sawant#MachineLearning #DecisionTree #DataScience #Python #AI #Coding #Learning #JupyterNotebook #CSE #PRMCEAM