**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();
deque.addLast(i);
}
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]
```

## View More Similar Problems

## Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

View Solution →## Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

View Solution →## Components in a graph

There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu

View Solution →## Kundu and Tree

Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that

View Solution →## Super Maximum Cost Queries

Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and

View Solution →## Contacts

We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co

View Solution →