Longest Equivalent Sublist After K Increments - Google Top Interview Questions
Problem Statement :
You are given a list of integers nums and an integer k. Consider an operation where you increment any one element once. Given that you can perform this at most k times, return the length of the longest sublist containing equal elements. Constraints n ≤ 100,000 where n is the length of nums k < 2 ** 31 Example 1 Input nums = [2, 4, 8, 5, 9, 6] k = 6 Output 3 Explanation We can increment 8 once and 5 four times to get a sublist of [9, 9, 9].
Solution :
Solution in C++ :
int solve(vector<int>& nums, int k) {
int ans = 0;
multiset<int> m;
for (int i = 0, j = 0, sum = 0; j < nums.size(); j++) {
sum += nums[j];
m.insert(nums[j]);
for (; !m.empty() && *m.rbegin() * (j - i + 1) - sum > k; i++) {
m.erase(m.find(nums[i]));
sum -= nums[i];
}
ans = max(ans, j - i + 1);
}
return ans;
}
Solution in Java :
import java.util.*;
class Solution {
public int solve(int[] nums, int k) {
MultiSet ms = new MultiSet();
int l = 0;
int r = 0;
int cur_increments = 0;
int ret = 0;
// move r until necessary increments exceeds k
// anchor l until it's valid again
while (r < nums.length) {
// process r
Integer maxy = ms.last();
int x = nums[r];
if (maxy == null || x > maxy) {
if (maxy != null) {
cur_increments += (x - maxy) * ms.size();
}
} else {
cur_increments += (maxy - x);
}
ms.add(x);
// process l
while (cur_increments > k) {
x = nums[l];
ms.remove(x);
int lmaxy = ms.last();
if (lmaxy == x) {
} else if (lmaxy < x) {
cur_increments -= ms.size() * (x - lmaxy);
} else {
cur_increments -= lmaxy - x;
}
l++;
}
ret = Math.max(ret, r - l + 1);
r++;
}
return ret;
}
}
class MultiSet {
TreeMap<Integer, Integer> map = new TreeMap<>();
private int size = 0;
public MultiSet() {
}
public void add(int val) {
map.put(val, map.getOrDefault(val, 0) + 1);
size++;
}
public void remove(int val) {
map.put(val, map.get(val) - 1);
if (map.get(val) == 0) {
map.remove(val);
}
size--;
}
public int size() {
return size;
}
public Integer higher(int val) {
return map.higherKey(val);
}
public Integer lower(int val) {
return map.lowerKey(val);
}
public Integer ceiling(int val) {
return map.ceilingKey(val);
}
public Integer floor(int val) {
return map.floorKey(val);
}
public Integer first() {
if (map.isEmpty())
return null;
return map.firstKey();
}
public Integer last() {
if (map.isEmpty())
return null;
return map.lastKey();
}
public boolean isEmpty() {
return map.isEmpty();
}
@Override
public String toString() {
return map.toString();
}
}
Solution in Python :
class Solution:
def solve(self, nums, k):
ans = left = total = 0
q = deque()
for right, a in enumerate(nums):
total += a
while q and nums[q[-1]] <= a:
q.pop()
q.append(right)
while q and k < (right - left + 1) * nums[q[0]] - total:
total -= nums[left]
if q and left == q[0]:
q.popleft()
left += 1
ans = max(ans, right - left + 1)
return ans
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 →