Remove sublist from list Python

Program to remove sublist to get same number of elements below and above k in C++

C++Server Side ProgrammingProgramming

Suppose we have a list of numbers called nums and another number k, we can remove any sublist at most once from the list. We have to find the length of the longest resulting list such that the amount of numbers strictly less than k and strictly larger than k is the same.

Nội dung chính Show

Program to remove sublist to get same number of elements below and above k in C++

So, if the input is like nums = [6, 10, 8, 9, 3, 5], k = 6, then the output will be 5, as if we remove the sublist [9] then we will get [6, 10, 8, 3, 5] and there are two numbers [3, 5] which are smaller than 6 and two numbers [10, 8] larger than 6.

To solve this, we will follow these steps

Define an array v of size same as nums + 1 and fill with 0
cnt := 0
for initialize i := 0, when i < size of nums, update (increase i by 1), do
- if nums[i] < k, then:
  - (increase cnt by 1)
- otherwise when nums[i] > k, then:
  - (decrease cnt by 1)
- v[i + 1] = cnt
if last element of v is 0, then return size of nums
- delta := last element of v
Define one map m
ans := infinity
for initialize i := 1, when i <= size of v, update (increase i by 1), do
- if m[v[i] - last element of v] is not equal to 0 or (v[i] - last element of v is same as 0), then
  - ans := minimum of ans and i - m[v[i] - last element of v]
- m[v[i]] := i
if ans is same as infinity, then
- return 0
Otherwise
- return size of nums

Let us see the following implementation to get better understanding

Example

Live Demo

#include <bits/stdc++.h> using namespace std; class Solution { public: int solve(vector<int>& nums, int k) { vector<int> v(nums.size() + 1, 0); int cnt = 0; for (int i = 0; i < nums.size(); ++i) { if (nums[i] < k) ++cnt; else if (nums[i] > k) --cnt; v[i + 1] = cnt; } if (v.back() == 0) return int(nums.size()); int delta = v.back(); map<int, int> m; int ans = INT_MAX; for (int i = 1; i <= v.size(); ++i) { if (m[v[i] - v.back()] != 0 || v[i] - v.back() == 0) { ans = min(ans, i - m[v[i] - v.back()]); } m[v[i]] = i; } if (ans == INT_MAX) return 0; else return int(nums.size() - ans); } }; main(){ Solution ob; vector<int> v = {6, 10, 8, 9, 3, 5}; int k = 6; cout << ob.solve(v, k); }