Stokastik

Machine Learning, AI and Programming

Category: PROBLEM SOLVING

Leetcode : The Skyline Problem

Problem Statement Solution: It was actually difficult for me to come up with the brute force approach to solve the skyline problem. But that does not mean that getting to the efficient solution was easy. I struggled a lot in order to come to the efficient solution because there were so many scenarios that I was missing out on initially. Coming to think of it, the brute force approach would […]

Continue Reading →

Leetcode : Sliding Window Median

Problem Statement Solution: The brute force approach to solve this problem is to sort the numbers in each window and then compute the median for each window. Since there are K numbers in each window, thus the run-time complexity of the brute force approach is O(N*K*logK) because, there are N-K windows and sorting each window is O(K*logK).

Continue Reading →

Leetcode : Consecutive Numbers Sum

Problem Statement Solution: The brute force approach is to evaluate all possible sequence of consecutive numbers less than N, whose sum gives N. The number of all possible sequences of consecutive numbers less than N is O(N2), because we can select pair of indices i and j (i <= j) such that the sequence lies between i and j. The number of such pairs is O(N2). We can definitely improve […]

Continue Reading →

Leetcode : Non-negative Integers without Consecutive Ones

Problem Statement Solution: The brute force approach is to scan all the integers less than equals to N, compute their binary representation and check if the binary representation has consecutive ones or not. The run-time complexity of this approach is O(N*logN) because scanning all the integers less than N is O(N) and scanning the binary representation for each integer is O(logN), because binary representation of an integer M is of […]

Continue Reading →

Leetcode : K-Similar Strings

Problem Statement Solution: The brute force approach is to evaluate all possible swaps. Given the string is of length N, the number of possible pairs is U=0.5*N*(N-1). But observe that not just the swaps but the sequence of swaps also matters. The number of possible sequence of swaps is U!. Thus the run-time complexity is O(U!). For moderately sized value of N such as 20 as given by the problem […]

Continue Reading →

Leetcode : Reverse Pairs

Problem Statement Solution: The brute force approach is to consider all pairs (i, j) such that i < j and check whether they satisfy the condition that nums[i] > 2*nums[j]. The time complexity for this approach is definitely O(N2) where N is the number of elements in the array 'nums'. We can improve this time complexity by reducing the number of comparisons required for each element. For e.g. if we […]

Continue Reading →

Detecting placeholder images in e-Commerce product listings

Many times we trust sellers to upload correct product images for online products on our e-commerce platform, but due to checks in place that a product shall always accompany an image, 3rd party sellers upload stock or placeholder image in case there is no image for the product available. Problem is that although we do not want to show products without images on our website, but due to zero validation […]

Continue Reading →

Leetcode : Bricks Falling When Hit

Problem Statement Solution: This is a trick problem. I will come later to explain why. So the most logical approach to solve the problem is to first 'hit & erase' one of the brick A and then for each of the adjacent bricks of A, check if they are 'connected' to the top of the grid. If they are connected to the top of the grid don't do anything, else […]

Continue Reading →

Leetcode : Longest Valid Parentheses

Problem Statement Solution: Most of us must have encountered a similar problem of finding the maximum number of valid parentheses pairs, which is pretty straightforward and quite commonly asked in many programming interviews. This is one variant where we need to find the longest sub-string which is a valid parentheses. The sub-string may contain any number of parenthesis pairs. One naive approach is to check for all pair of indices […]

Continue Reading →

Leetcode : Count The Repetitions

Problem Statement Solution: One naive approach is to estimate the value of M from the fact that the maximum value of M possible is: Q=(n1*len(s1))/(n2*len(s2)) Let s(x) denote the string s repeated 'x' times. Using binary search between 0 to Q, check if the string s2(n2*m) is present in the string s1(n1) for some m. If s2(n2*m) is present in s1(n1), then search to the right half of m else to the left […]

Continue Reading →