Uploaded January 2019 | Updated November 2026, 3 hours ago
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given an array of all integers that may or may not be sorted, determine the length of the longest subsequence that is strictly non-decreasing.
What Is A Subsequence?
A subsequence of an array is a subset of the array that maintains temporal order.
It does not have to be contiguous but it might turn out to be contiguous by chance.
Problem Name / Variants
This problem also comes in the form of asking for the longest strictly decreasing subsequence.
This is longest non-decreasing subsequence meaning that we will have a non-strictly increasing subsequence (aka we can have deltas of 0 between contiguous elements in the subsequence).
Approach 1 (Brute Force)
We can enumerate all 2^n subsets of the original array and then test them for the non-decreasing property.
The answer will be the longest subset that has the property.
This is too expensive.
Approach 2 (Dynamic Programming)
Do you see the potential for a subproblem here?
If you do, then we have the opportunity to use dynamic programming.
Example
[ -1, 3, 4, 5, 2, 8 ]
At the index 0 I always know that I can have a subsequence of length 1.
In fact, at all positions the longest non-decreasing subsequence can be at least length 1.
We then look at index 1, I need to ask myself if the item at index 1 can lengthen the longest subseqence found at index 0.
We check if 3 is greater than or equal to 1...it is. Great. index 1 can be tacked on but...should I?
The LNDS (longest non-decreasing subsequence) at index 1 is 0.
The LNDS at index 0 is 1.
Yeah...it makes sense because if I tack 3 onto the LNDS I found for the subproblem of just [ -1 ] then at index 1 I will also have a LDNS.
So what we basically do is build a table and ask ourselves these questions all along the way.
EACH CELL REPRESENTS THE ANSWER TO THE SUBPROBLEM ASKED AGAINST the subsequence from index 0 to index i (including the element at index i).
Complexities:
Time: O( n^2 )
n is the length of the array.
For each of the n elements we will solve the LNDS problem which takes O(n) time, therefore we yield a O( n^2 ) runtime complexity.
Space: O( n )
We will store our answers for each of the n LNDS subproblems.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 17.12 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given an array of all integers that may or may not be sorted, determine the length of the longest subsequence that is strictly non-decreasing.
What Is A Subsequence?
A subsequence of an array is a subset of the array that maintains temporal order.
It does not have to be contiguous but it might turn out to be contiguous by chance.
Problem Name / Variants
This problem also comes in the form of asking for the longest strictly decreasing subsequence.
This is longest non-decreasing subsequence meaning that we will have a non-strictly increasing subsequence (aka we can have deltas of 0 between contiguous elements in the subsequence).
Approach 1 (Brute Force)
We can enumerate all 2^n subsets of the original array and then test them for the non-decreasing property.
The answer will be the longest subset that has the property.
This is too expensive.
Approach 2 (Dynamic Programming)
Do you see the potential for a subproblem here?
If you do, then we have the opportunity to use dynamic programming.
Example
[ -1, 3, 4, 5, 2, 8 ]
At the index 0 I always know that I can have a subsequence of length 1.
In fact, at all positions the longest non-decreasing subsequence can be at least length 1.
We then look at index 1, I need to ask myself if the item at index 1 can lengthen the longest subseqence found at index 0.
We check if 3 is greater than or equal to 1...it is. Great. index 1 can be tacked on but...should I?
The LNDS (longest non-decreasing subsequence) at index 1 is 0.
The LNDS at index 0 is 1.
Yeah...it makes sense because if I tack 3 onto the LNDS I found for the subproblem of just [ -1 ] then at index 1 I will also have a LDNS.
So what we basically do is build a table and ask ourselves these questions all along the way.
EACH CELL REPRESENTS THE ANSWER TO THE SUBPROBLEM ASKED AGAINST the subsequence from index 0 to index i (including the element at index i).
Complexities:
Time: O( n^2 )
n is the length of the array.
For each of the n elements we will solve the LNDS problem which takes O(n) time, therefore we yield a O( n^2 ) runtime complexity.
Space: O( n )
We will store our answers for each of the n LNDS subproblems.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 17.12 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.



![Find the kth Largest or Smallest Element of an Array: From Sorting To Heaps To Partitioning
Code & Problem Statement @ https://backtobackswe.com/platform/content/find-the-kth-largest-or-smallest-element/video?utm_source=youtube&utm_medium=video
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given an array and k, find the kth largest element as efficiently as possible. Return the actual value of the kth largest item.
I got this question in my final round of Facebook internship interviews...this is before I knew how to solve recurrences and analyze algorithms, etc...I fucked it up but who cares...I talked for so long and thought the optimal solution was log(n)...but I was really wrong.
Approaches
Sort: O(n*log(n))
Use A Min-Heap: O(n*log(k))
Remember QuickSort...how does it work...what does it fundamentally do...partition
The kth largest element will be at index n - k
Ex:
arr = [ 3, 2, 1, 5, 6, 4 ]
k = 2
The first largest element should be at the last index ... index 5 ... (6) - (1) = 5
The 2nd largest element should be at index (6) - (2) = 4
The nth largest element should be at the first index ... index 0 ... (6) - (6) = 0
So...
finalPivotPosition n - k ... The pivot is the kth largest element
finalPivotPosition greater than n - k ... kth largest must be in the left partition
finalPivotPosition less than n - k ... kth largest must be in the right partition
We an pick a pivot however we want but random is best since we have a equal likelihood to pick any element.
The worst case is O(nΒ²) but the likelihood this can happen goes down exponentially because it can only happen if the greatest or least item is chosen as a pivot repeatedly.
Complexities
Time: O(n)
On average we will be splitting the input in half leading to a recurrence of T(n) = T(n/2) + (n - 1)
If we solve for these exact amount of comparisons we see that we stay to the order of linear time.
Space: O(1)
Everything is done in-place.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is question 12.8 in the fantastic book Elements of Programming Interviews. Find the kth Largest or Smallest Element of an Array: From Sorting To Heaps To Partitioning](https://i.ytimg.com/vi/hGK_5n81drs/mqdefault.jpg)






![The Change Making Problem - Fewest Coins To Make Change Dynamic Programming
Code & Problem Statement @ https://backtobackswe.com/platform/content/the-change-making-problem/video?utm_source=youtube&utm_medium=video
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Examples:
1
Input:: coins = [1, 2, 5], amount = 11
Output 3
2
Input: coins = [2], amount = 3
Output: -1
Approach 1 (Brute Force)
We can generate all sets of coin frequencies that end up summing to the total amount given the coins that we granted and then take the sequence with the least coins in it.
This is not only harder to implement, but it entails an automatic exponential amount of work to compute all the sets of coin frequencies to only take the best answer (the set with the least coins) from.
Approach 2 (Top Down Dynamic Programming)
Example:
Input:: coins = [1, 2, 5], amount = 11
Output 3
The answer to the subproblem for amount 11 is the same thing as the MINIMUM of the answers to the sub problems with each currency deduced from the original sub problem (11) PLUS ONE since we are acting as if each coin we subtract from 11 is the last coin used to make change.
Not all paths will yield an answer, some will yield an optimal answer.
Complexities (Top Down)
A is the amount to make change for.
n is the total denominations avaliable to make change with.
Time: O( A * n )
For each amount we will approximately be doing n work in trying to deduct each denomination from the current sub problem
Our recursive tree will at maximum have a depth of S (worst case if each call deducts 1 at each call).
Space: O( A )
We answer and store a total of A subproblems in our dynamic programming table to get to our globally optimum answer.
Approach 3 (Bottom Up Dynamic Programming)
Example:
Input:: coins = [1, 2, 5], amount = 11
Output 3
We can also create a dynamic programming table going from the bottom up to the amount we want an answer for.
Complexities (Bottom Up)
A is the amount to make change for.
n is the total denominations avaliable to make change with.
Time: O( A * n )
For each amount we will potentially try each of the denominations (there are n of them).
Space: O( A )
We answer and store a total of A subproblems in our dynamic programming table to get to our globally optimum answer.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw The Change Making Problem - Fewest Coins To Make Change Dynamic Programming](https://i.ytimg.com/vi/jgiZlGzXMBw/mqdefault.jpg)