1st question: Something like minimum number of swaps to put min value of a list in the leftmost position and max value in the rightmost position. Condition: You can swap only the adjacent numbers in the list at a single time.
Example:
list = [6, 9, 4, 1, 5]
Output = 5
Explanation: It will take 5 minimum swaps to put min value in leftmost and max value in rightmost position.
[1, 6, 4, 5, 9]Passed all 15 test cases in 1st Qs.
2nd question: Almost similar to https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/. Only difference in condition was, Max - Min <= Target
Example:
list = [1, 10, 2], k = 9
For [1], max = 1, min =1, max - min = 1 - 1 = 0 <= 9, Condition satisfied
For [1,10], max = 10, min =1, max - min = 10 - 1 = 9 <= 9, Condition satisfied
For [1, 10, 2], max = 10, min =1, max - min = 10 - 1 = 9 <= 9, Condition satisfied
For [10], max = 10, min =10, max - min = 10 - 10 = 0 <= 9, Condition satisfied
For [10, 2], max = 10, min =2, max - min = 10 - 2 = 8 <= 9, Condition satisfied
For [2], max = 2, min =2, max - min = 2 - 2 = 0 <= 9, Condition satisfied
Output = 6 (All subarrays satisfied)Did a brute-force solution to 2nd Qs. Passed 9 test cases and rest were TLE.
Any suggestions for an optimal solution to this Qs?
Comments (11)