Neha Bhatia’s Post

🌳 **Day 137: Find the Kth Smallest Element in a Binary Search Tree (BST)** **Understanding the Problem:** We are given a binary search tree (BST) and an integer K. We need to find the Kth smallest element in the BST. Since the BST is structured in a way that an inorder traversal yields the nodes in sorted order, we can leverage this property. **Approach:** To solve this problem, we use an inorder traversal to visit the nodes in sorted order. We keep a counter to track the number of nodes visited and stop once we reach the Kth node. **Implementation:** 1. **Helper Function for Inorder Traversal:**   - Define a helper function `solve` that performs an inorder traversal of the BST.   - Use a counter to track the number of nodes visited.   - If the counter matches K, set the answer to the current node's value. 2. **Main Function to Find Kth Smallest Element:**   - Initialize the answer and counter variables.   - Call the helper function to start the inorder traversal.   - Return the answer once the traversal is complete. **Steps:** 1. Traverse the BST in inorder fashion. 2. Increment the counter each time a node is visited. 3. Once the counter matches K, capture the node's value as the answer. 4. Continue traversal until the Kth node is found. **Complexity Analysis:** - Time Complexity: O(N), where N is the number of nodes in the BST. In the worst case, we might need to visit all nodes. - Space Complexity: O(H), where H is the height of the BST. This space is used for the recursive call stack. This approach efficiently finds the Kth smallest element in a binary search tree. 🌟 #BinarySearchTree #KthSmallestElement #DSADay137 #AlgorithmInsights

The first step towards an understanding of why the study and knowledge of algorithms are so important is to define exactly what we mean by an algorithm. According to the popular algorithms textbook Introduction to Algorithms (Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein), "an algorithm is any well- defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values as output." In other words, algorithms are like road maps for accomplishing a given, well-defined task. So, a chunk of code that calculates the terms of the Fibonacci sequence is an implementation of a particular algorithm. Even a simple function for adding two numbers is an algorithm in a sense, albeit a simple one.

Day 41 of #100DaysOfCode Problem : Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n]. Example 1: Input: n = 13, k = 2 Output: 10 Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10. Example 2: Input: n = 1, k = 1 Output: 1 Constraints: 1 <= k <= n <= 109

🌟 Day 2 of the GeeksforGeeks 160 Days Challenge Today's task: Implement KMP Algorithm for Pattern Searching 🔍 This problem emphasizes how efficient string matching can be achieved using the Knuth-Morris-Pratt (KMP) algorithm. Optimizing search operations for large texts is a key area for improvement in computational efficiency.🚀 🔍 Problem Statement: Given a pattern and a text, the task is to find all occurrences of the pattern in the text using the KMP algorithm. Return a list of indices where the pattern starts in the text. 🛠️ Solution Approach: Here's a breakdown of the KMP algorithm that I implemented: 1️⃣ Preprocessing with LPS (Longest Prefix Suffix) Array: Constructed an LPS array for the given pattern. This array helps avoid unnecessary re-checking of characters in the pattern, improving the time complexity of the search phase. For each character in the pattern, the LPS array tracks the length of the longest prefix that is also a suffix for the substring ending at that character. 2️⃣ Pattern Searching with KMP: I iterated through the text using two pointers, one for the pattern and one for the text. Whenever a mismatch occurred, the KMP algorithm efficiently shifts the pattern based on the LPS array, reducing the number of comparisons needed. Once a full match is found, I added the starting index of the match to the result list and continued searching with the help of the LPS values.

Our new article "On Improvements of Multi-Objective Branch and Bound" co-authored by Dr. Julius Bauß and Sophie Parragh is published in the EURO Journal on Computational Optimization. We improve the performance of multi-objective branch and bound by using objective space information to guide the search in promising directions and to obtain good approximations of the Pareto front in early stages of the algorithm. In particular, we use an indicator-based scheduling of subproblems and the solution of adaptively chosen scalarizations to integer optimality. EURO Journal on Computational Optimization (Open access) https://lnkd.in/e_HvgEYN

🚀🌳 Day 25 of #100DaysOfCode 🔍 Today, I focused on finding the kth smallest element in a Binary Search Tree (BST), which utilizes the in-order traversal approach to efficiently retrieve sorted elements. Problem: Retrieve the kth smallest element from a BST. Key Insight: Since an in-order traversal of a BST produces nodes in ascending order, the kth element in this traversal is the desired result Approach: Perform an in-order traversal (left-root-right) to visit nodes in ascending order. Keep track of nodes visited and stop at the kth node, which provides the kth smallest element. Iterative Approach: Alternatively, using an iterative stack-based traversal can be memory-efficient and avoids recursion stack limits in large trees. Edge Cases: k is out of range (greater than the number of nodes or less than 1). The BST has only one node. k equals the number of nodes (returns the largest element). Complexity Analysis Time Complexity: O(h + k), where h is the tree height and k is the number of nodes traversed. In a balanced BST, this averages to O(log n + k). Space Complexity: O(h), for the stack in the iterative approach or recursion depth in recursive traversal. Learning In-order traversal's natural sorting property is particularly powerful when solving for the kth smallest or largest elements. #BinarySearchTree #KthSmallestElement #InOrderTraversal #BSTTraversal

I am very happy to share that our new article "On improvements of multi-objective branch and bound" co-authored by Michael Stiglmayr and Sophie Parragh has been published in the EURO Journal on Computational Optimization. Branch and bound methods which are based on the principle “divide and conquer” are a well established solution approach in single-objective integer programming. In multi-objective optimization, branch and bound algorithms are increasingly attracting interest. However, the larger number of objectives raises additional difficulties for implicit enumeration approaches like branch and bound. Since bounding and pruning is considerably weaker in multiple objectives, many branches have to be (partially) searched and may not be pruned directly. The adaptive use of objective space information can guide the search in promising directions to determine a good approximation of the Pareto front already in early stages of the algorithm. In particular, we focus in this article on improving the branching and queuing of subproblems and the handling of lower bound sets. In our numerical tests, we evaluate the impact of the proposed methods in comparison to a standard implementation of multi-objective branch and bound on knapsack problems, generalized assignment problems and (un)capacitated facility location problems.

Insertion sort is a simple and intuitive sorting algorithm that builds the final sorted array one element at a time Let's take a look at how it works: Start with the Second Element: Assume the first element is already sorted. Take the second element and find its correct position in the sorted part of the array, then insert it there. Repeat for All Elements: Move to the next element and repeat the process until the entire array is sorted. Time Complexity: O(n^2) Space Complexity: O(1) because it sorts the list in place. #DSA #SDE #ALGORITHIMS

Human matting is a foundation task in image and video processing where human foreground pixels are extracted from the input. Prior works either improve the accuracy by additional guidance or improve the temporal consistency of a single instance across frames. This Paper proposes a new framework MaGGIe, Masked Guided Gradual Human Instance Matting, which predicts alpha mattes progressively for each human instance while maintaining the computational cost, precision, and consistency. The method leverages modern architectures, including transformer attention and sparse convolution, to output all instance mattes simultaneously without exploding memory and latency. Code and datasets are available at 👉 https://lnkd.in/g5NGetUY. Paper 👉 https://lnkd.in/gRakdity

Geek For Geeks Question https://lnkd.in/gZyUqVjP Problem Statement:  Given an array arr of size n and an integer X. Find if there's a triplet in the array which sums up to the given integer X. My Solution:  Using Hashing: This approach uses extra space. Here we will have 2 loops one outer loop and another inner loop from i + 1. Check if the given remainder is in the dictionary if it is we have our result else we will push the inner loop value into dictionary. class Solution: def find3Numbers(self, A, n, X): numbers = {A[0]: 1} for i in range(1, n): j = i + 1 while j < n: remainder = X - (A[i] + A[j]) if(remainder in numbers and (A[i] != remainder and A[j] != remainder)): return True else: numbers[A[j]] = 1 j += 1 else: return False Time Complexity: O(N2), Space Complexity: O(N) Other Solution:  Using the Two Pointers: Initially Sorting the array. Then run 2 loops the outer loop on the list and inner loop will with 2 pointers. Moving the left pointer if sum is less that X and right pointer if sum is greater than X. class Solution: def find3Numbers(self, A, n, X): A.sort() for i in range(0, n): left = i + 1 right = n - 1 while left < right: sum = A[i] + A[left] + A[right] if sum == X: return True else: if sum > X: right -= 1 else: left += 1 else: return False Time Complexity: O(N2), Space Complexity: O(1) #gfgcodechallenge #dsachallenge #algorithms #binarysearch #hashing