# Tag: Leetcode

## 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).

## 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 […]

## 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 […]

## 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 […]

## 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 […]

## 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 […]

## 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 […]