# K Lexicographically Smallest Subsequence - Google Top Interview Questions

### Problem Statement :

```Given a list of integers nums and an integer k, return the lexicographically smallest subsequence of length k.

Constraints

k ≤ n ≤ 100,000 where n is the length of nums

Example 1

Input

nums = [1, 2, 0, 9, 2, 3]

k = 3

Output

[0, 2, 3]

Example 2

Input

nums = [10, 1, 0]

k = 2

Output

[1, 0]```

### Solution :

```                        ```Solution in C++ :

vector<int> solve(vector<int>& nums, int k) {
int n = nums.size();
stack<int> st;
for (int i = 0; i < n; i++) {
if (st.empty())
st.push(nums[i]);

else if (st.top() > nums[i]) {
if (n - i >= k) {
while (!st.empty() and st.top() > nums[i]) st.pop();
st.push(nums[i]);
} else if (st.size() + n - i >= k) {
while (!st.empty() and st.size() + n - i > k and st.top() > nums[i]) st.pop();
st.push(nums[i]);
} else {
st.push(nums[i]);
}
} else {
st.push(nums[i]);
}
}
while (!st.empty() and st.size() > k) st.pop();
vector<int> ans;
while (!st.empty()) {
ans.push_back(st.top());
st.pop();
}
reverse(begin(ans), end(ans));
return ans;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int[] solve(int[] nums, int k) {
if (nums == null || nums.length == 0 || k > nums.length)
return new int[0];
Deque<Integer> deque = new ArrayDeque();
for (int i = 0; i < nums.length; i++) {
while (!deque.isEmpty() && nums[i] < nums[deque.peekLast()]
&& (nums.length - (i + 1)) >= k - deque.size())
deque.pollLast();
}
int[] res = new int[k];
for (int i = 0; i < k; i++) res[i] = nums[deque.pollFirst()];
return res;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, nums, k):
if k <= 0:
return []

n = len(nums)
stack = []

for index, num in enumerate(nums):
while stack and num < stack[-1] and (len(stack) + n - index - 1) >= k:
stack.pop()
stack.append(num)

return stack[:k]```
```

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element