Sorted Subsegments – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Sorted Subsegments HackerRank Solution
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }
typedef char Val;
struct Sum {
int cnt;
Sum() : cnt(0) {}
Sum(const Val &val, int pos) : cnt(val) {}
Sum &operator+=(const Sum &that) { cnt += that.cnt; return *this; }
Sum operator+(const Sum &that) const { return Sum(*this) += that; }
};
struct Add {
int assign;
Add() : assign(-1) {}
explicit Add(int a) : assign(a) {}
Add &operator+=(const Add &that) {
if(that.assign != -1)
assign = that.assign;
return *this;
}
void addToVal(Val &val, int pos) const {
if(assign != -1)
val = assign != 0;
}
void addToSum(Sum &sum, int left, int right) const {
if(assign != -1)
sum.cnt = assign != 0 ? right - left : 0;
}
};
struct SegmentTree {
vector<Val> leafs;
vector<Sum> nodes;
vector<Add> add;
vector<int> leftpos, rightpos;
int n, n2;
void init(int n_, const Val &v = Val()) { init(vector<Val>(n_, v)); }
void init(const vector<Val> &u) {
n = 1; while(n < (int)u.size()) n *= 2;
n2 = (n - 1) / 2 + 1;
leafs = u; leafs.resize(n, Val());
nodes.resize(n);
for(int i = n - 1; i >= n2; -- i)
nodes[i] = Sum(leafs[i * 2 - n], i * 2 - n) + Sum(leafs[i * 2 + 1 - n], i * 2 + 1 - n);
for(int i = n2 - 1; i > 0; -- i)
nodes[i] = nodes[i * 2] + nodes[i * 2 + 1];
add.assign(n, Add());
leftpos.resize(n); rightpos.resize(n);
for(int i = n - 1; i >= n2; -- i) {
leftpos[i] = i * 2 - n;
rightpos[i] = (i * 2 + 1 - n) + 1;
}
for(int i = n2 - 1; i > 0; -- i) {
leftpos[i] = leftpos[i * 2];
rightpos[i] = rightpos[i * 2 + 1];
}
}
Val get(int i) {
int indices[128];
int k = getIndices(indices, i, i + 1);
propagateRange(indices, k);
return leafs[i];
}
Sum getRangeCommutative(int i, int j) {
int indices[128];
int k = getIndices(indices, i, j);
propagateRange(indices, k);
Sum res = Sum();
for(int l = i + n, r = j + n; l < r; l >>= 1, r >>= 1) {
if(l & 1) res += sum(l ++);
if(r & 1) res += sum(-- r);
}
return res;
}
Sum getRange(int i, int j) {
int indices[128];
int k = getIndices(indices, i, j);
propagateRange(indices, k);
Sum res = Sum();
for(; i && i + (i&-i) <= j; i += i&-i)
res += sum((n + i) / (i&-i));
for(k = 0; i < j; j -= j&-j)
indices[k ++] = (n + j) / (j&-j) - 1;
while(-- k >= 0) res += sum(indices[k]);
return res;
}
void set(int i, const Val &x) {
int indices[128];
int k = getIndices(indices, i, i + 1);
propagateRange(indices, k);
leafs[i] = x;
mergeRange(indices, k);
}
void addToRange(int i, int j, const Add &x) {
if(i >= j) return;
int indices[128];
int k = getIndices(indices, i, j);
propagateRange(indices, k);
int l = i + n, r = j + n;
if(l & 1) { int p = (l ++) - n; x.addToVal(leafs[p], p); }
if(r & 1) { int p = (-- r) - n; x.addToVal(leafs[p], p); }
for(l >>= 1, r >>= 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) add[l ++] += x;
if(r & 1) add[-- r] += x;
}
mergeRange(indices, k);
}
private:
int getIndices(int indices[], int i, int j) const {
int k = 0, l, r;
if(i >= j) return 0;
for(l = (n + i) >> 1, r = (n + j - 1) >> 1; l != r; l >>= 1, r >>= 1) {
indices[k ++] = l;
indices[k ++] = r;
}
for(; l; l >>= 1) indices[k ++] = l;
return k;
}
void propagateRange(int indices[], int k) {
for(int i = k - 1; i >= 0; -- i)
propagate(indices[i]);
}
void mergeRange(int indices[], int k) {
for(int i = 0; i < k; ++ i)
merge(indices[i]);
}
inline void propagate(int i) {
if(i >= n) return;
add[i].addToSum(nodes[i], leftpos[i], rightpos[i]);
if(i * 2 < n) {
add[i * 2] += add[i];
add[i * 2 + 1] += add[i];
} else {
add[i].addToVal(leafs[i * 2 - n], i * 2 - n);
add[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1 - n);
}
add[i] = Add();
}
inline void merge(int i) {
if(i >= n) return;
nodes[i] = sum(i * 2) + sum(i * 2 + 1);
}
inline Sum sum(int i) {
propagate(i);
return i < n ? nodes[i] : Sum(leafs[i - n], i - n);
}
};
int main() {
int n; int q; int k;
while(~scanf("%d%d%d", &n, &q, &k)) {
vector<int> A(n);
for(int i = 0; i < n; ++ i)
scanf("%d", &A[i]);
vector<int> l(q), r(q);
for(int i = 0; i < q; ++ i)
scanf("%d%d", &l[i], &r[i]), ++ r[i];
vi values = A;
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
int lo = 0, up = (int)values.size() - 1;
while(up - lo > 0) {
int mid = (lo + up + 1) / 2;
vector<Val> initvals(n);
rep(i, n)
initvals[i] = values[mid] <= A[i];
SegmentTree segt; segt.init(initvals);
rep(i, q) {
int cnt0 = r[i] - l[i] - segt.getRangeCommutative(l[i], r[i]).cnt;
segt.addToRange(l[i], l[i] + cnt0, Add(0));
segt.addToRange(l[i] + cnt0, r[i], Add(1));
}
if(segt.get(k))
lo = mid;
else
up = mid - 1;
}
printf("%d\n", values[lo]);
}
return 0;
}
Java Sorted Subsegments HackerRank Solution
import java.io.*;
import java.util.*;
public class Solution {
private static InputReader in;
private static PrintWriter out;
public static int[] brr;
static class SegmentTree {
public SegmentTree left, right;
public int nones, start, end;
public int pushval;
public SegmentTree(int start, int end) {
this.start = start;
this.end = end;
this.pushval = -1;
if (start != end) {
int mid = (start + end) >> 1;
left = new SegmentTree(start, mid);
right = new SegmentTree(mid+1, end);
nones = left.nones + right.nones;
} else {
nones = brr[start] == 1 ? 1 : 0;
}
}
public int size() {
return end-start+1;
}
public void push() {
if (left == null) return;
if (pushval == -1) return;
left.nones = pushval == 1 ? left.size() : 0;
left.pushval = pushval;
right.nones = pushval == 1 ? right.size() : 0;
right.pushval = pushval;
pushval = -1;
}
public void join() {
if (left == null) return;
this.nones = left.nones+right.nones;
}
public int count(int s, int e) {
if (start == s && end == e) return nones;
push();
int mid = (start + end) >> 1;
if (mid >= e) return left.count(s, e);
else if (mid < s) return right.count(s,e);
else return left.count(s,mid)+right.count(mid+1,e);
}
public void set(int s, int e, int val) {
if (s > e) return;
if (start == s && end == e) {
this.pushval = val;
this.nones = val == 1 ? this.size() : 0;
return;
}
push();
int mid = (start+end) >> 1;
if (mid >= e) {left.set(s, e, val);}
else if (mid < s) {right.set(s,e,val);}
else {
left.set(s,mid,val);
right.set(mid+1,e,val);
}
join();
}
}
public static void main(String[] args) throws IOException {
in = new InputReader(System.in);
out = new PrintWriter(System.out, true);
int n = in.nextInt(), q = in.nextInt(), k = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}
HashSet<Integer> dis = new HashSet<>();
for (int i = 0; i < n; i++) {
dis.add(arr[i]);
}
ArrayList<Integer> ls = new ArrayList<>(dis);
Collections.sort(ls);
int[] l = new int[q];
int[] r = new int[q];
for (int i = 0; i < q; i++) {
l[i] = in.nextInt();
r[i] = in.nextInt();
}
int lo = 0, hi = ls.size()-1;
while(lo<hi) {
int mid = (lo+hi+1) >> 1;
brr = new int[n];
for (int i = 0; i < n; i++) {
brr[i] = arr[i] < ls.get(mid) ? 0 : 1;
}
SegmentTree root = new SegmentTree(0, n-1);
for (int i = 0; i < q; i++) {
int a = root.count(l[i], r[i]);
root.set(l[i], r[i], 0);
root.set(r[i]-a+1, r[i], 1);
}
int x = root.count(k, k);
if (x == 1) {
lo = mid;
} else {
hi = mid-1;
}
}
out.println(ls.get(lo));
out.close();
System.exit(0);
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
Python 3 Sorted Subsegments HackerRank Solution
import sys
##### Read Data
dat = [x.split() for x in sys.stdin.readlines()]
N = int(dat[0][0])
Q = int(dat[0][1])
k = int(dat[0][2])
a = list(map(int, dat[1]))
q = [list(map(int, x)) for x in dat[2:len(dat)]]
##### Process Queries
b = sorted(a)
lmin, rmax, pmax, qmin = (N-1), 0, 0, (N-1)
pmin, qmax, flag = (N-1), 0, 1
count, span_q, ladder, revlad = [], 0, 0, 0
if Q >= 2:
ladder = all(q[i+1][0] > q[i][0] for i in range(Q-1))
revlad = all(q[i+1][1] < q[i][1] for i in range(Q-1))
if a != b and ladder < 1 and revlad < 1:
for i in range(Q):
l, r = q[i][0], q[i][1]
if (r-l) > (rmax-lmin):
lmin, rmax = l, r
if l < pmin:
pmin, pmax = l, r
elif l == pmin and pmax < r:
pmax = r
if r > qmax:
qmin, qmax = l, r
elif r == qmax and qmin > l:
qmin = l
for i in range(Q):
l, r = q[i][0], q[i][1]
if l > lmin and r < rmax: continue
if l > pmin and r < pmax: continue
if l > qmin and r < qmax: continue
if i < (Q-1):
if l >= q[i+1][0] and r <= q[i+1][1]:
continue
if i > 0:
if l >= q[i-flag][0] and r <= q[i-flag][1]:
flag += 1
continue
else:
flag = 1
count += [i]
span_q += r-l+1
# Perform Queries
if ladder > 0:
l, r, Qu = q[0][0], q[0][1], int((k+5)/5)
a[l:r+1] = sorted(a[l:r+1])
for i in range(1, Q):
l, r, r0, m, sig = q[i][0], q[i][1], q[i-1][1], 0, 0
if l > r0 or (r-r0) > 0.1*(r0-l):
a[l:r+1] = sorted(a[l:r+1])
continue
if k < l: break
count = list(range(r0+1, r+1))
for j in range(len(count)):
p, new_A = count[j], a[count[j]]
l, r0 = q[i][0], q[i-1][1]
if a[l] >= new_A:
del(a[p]); a[l:l] = [new_A]; continue
elif a[r0+j-1] <= new_A:
del(a[p]); a[r0+j:r0+j] = [new_A]; continue
while sig < 1:
m = int((l+r0)/2)
if a[m] > new_A:
r0 = m
elif a[m+1] < new_A:
l = m+1
else:
del(a[p]); a[m+1:m+1] = [new_A]
sig = 1
elif revlad > 0:
l, r, Qu = q[0][0], q[0][1], int((k+5)/5)
a[l:r+1] = sorted(a[l:r+1])
for i in range(1, Q):
l, r, l0, m, sig = q[i][0], q[i][1], q[i-1][0], 0, 0
if k > r: break
if r < l0:
a[l:r+1] = sorted(a[l:r+1]); continue
count = list(range(l, l0))
for j in range(len(count)):
p, new_A = count[j], a[count[j]]
if a[l0] >= new_A:
del(a[p]); a[l0:l0] = [new_A]; continue
elif a[r] <= new_A:
del(a[p]); a[r:r] = [new_A]; continue
while sig < 1:
m = int((l0+r)/2)
if a[m] > new_A:
r = m
elif a[m+1] < new_A:
l0 = m+1
else:
del(a[p]); a[m+1:m+1] = [new_A]
sig = 1
elif span_q < 1e9 and a != b:
for i in count:
l, r = q[i][0], q[i][1]
a[l:(r+1)] = sorted(a[l:(r+1)])
else:
a[pmin:qmax+1] = sorted(a[pmin:qmax+1])
print(a[k])
Python 2 Sorted Subsegments HackerRank Solution
import sys
##### Read Data
dat = [x.split() for x in sys.stdin.readlines()]
N = int(dat[0][0])
Q = int(dat[0][1])
k = int(dat[0][2])
a = list(map(int, dat[1]))
q = [list(map(int, x)) for x in dat[2:len(dat)]]
##### Process Queries
b = sorted(a)
lmin, rmax, pmax, qmin = (N-1), 0, 0, (N-1)
pmin, qmax, flag = (N-1), 0, 1
count, span_q, ladder, revlad = [], 0, 0, 0
if Q >= 2:
ladder = all(q[i+1][0] > q[i][0] for i in range(Q-1))
revlad = all(q[i+1][1] < q[i][1] for i in range(Q-1))
if a != b and ladder < 1 and revlad < 1:
for i in range(Q):
l, r = q[i][0], q[i][1]
if (r-l) > (rmax-lmin):
lmin, rmax = l, r
if l < pmin:
pmin, pmax = l, r
elif l == pmin and pmax < r:
pmax = r
if r > qmax:
qmin, qmax = l, r
elif r == qmax and qmin > l:
qmin = l
for i in range(Q):
l, r = q[i][0], q[i][1]
if l > lmin and r < rmax: continue
if l > pmin and r < pmax: continue
if l > qmin and r < qmax: continue
if i < (Q-1):
if l >= q[i+1][0] and r <= q[i+1][1]:
continue
if i > 0:
if l >= q[i-flag][0] and r <= q[i-flag][1]:
flag += 1
continue
else:
flag = 1
count += [i]
span_q += r-l+1
# Perform Queries
if ladder > 0:
l, r, Qu = q[0][0], q[0][1], int((k+5)/5)
a[l:r+1] = sorted(a[l:r+1])
for i in range(1, Q):
l, r, r0, m, sig = q[i][0], q[i][1], q[i-1][1], 0, 0
if l > r0 or (r-r0) > 0.1*(r0-l):
a[l:r+1] = sorted(a[l:r+1])
continue
if k < l: break
count = list(range(r0+1, r+1))
for j in range(len(count)):
p, new_A = count[j], a[count[j]]
l, r0 = q[i][0], q[i-1][1]
if a[l] >= new_A:
del(a[p]); a[l:l] = [new_A]; continue
elif a[r0+j-1] <= new_A:
del(a[p]); a[r0+j:r0+j] = [new_A]; continue
while sig < 1:
m = int((l+r0)/2)
if a[m] > new_A:
r0 = m
elif a[m+1] < new_A:
l = m+1
else:
del(a[p]); a[m+1:m+1] = [new_A]
sig = 1
elif revlad > 0:
l, r, Qu = q[0][0], q[0][1], int((k+5)/5)
a[l:r+1] = sorted(a[l:r+1])
for i in range(1, Q):
l, r, l0, m, sig = q[i][0], q[i][1], q[i-1][0], 0, 0
if k > r: break
if r < l0:
a[l:r+1] = sorted(a[l:r+1]); continue
count = list(range(l, l0))
for j in range(len(count)):
p, new_A = count[j], a[count[j]]
if a[l0] >= new_A:
del(a[p]); a[l0:l0] = [new_A]; continue
elif a[r] <= new_A:
del(a[p]); a[r:r] = [new_A]; continue
while sig < 1:
m = int((l0+r)/2)
if a[m] > new_A:
r = m
elif a[m+1] < new_A:
l0 = m+1
else:
del(a[p]); a[m+1:m+1] = [new_A]
sig = 1
elif span_q < 1e9 and a != b:
for i in count:
l, r = q[i][0], q[i][1]
a[l:(r+1)] = sorted(a[l:(r+1)])
else:
a[pmin:qmax+1] = sorted(a[pmin:qmax+1])
print(a[k])
C Sorted Subsegments HackerRank Solution
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
struct Query{
int l, r;
int ignore;
};
int ar1[75000];
int ar2[75000];
struct Query queries[75000];
struct Query sarea[75000];
int cmp(const void *a, const void *b){
return (*(int *)a - *(int *)b);
}
void insertionsort(int a[], int N){
int i, j;
int v;
for (i = 1; i < N; i++){
v = a[i];
for (j = i; j>0 && a[j - 1] > v; j--){
a[j] = a[j - 1];
}
a[j] = v;
}
}
int main() {
int n, q, k1, i, l, r, ign, j,mi,hr,nr,k,changed;
int si, sj;
int *a = ar1;
int *b = ar2;
scanf("%d %d %d", &n, &q, &k1);
for (i = 0; i<n; i++){
scanf("%d", &a[i]);
}
for (i = 0; i<q; i++){
scanf("%d %d", &(queries[i].l), &(queries[i].r));
queries[i].ignore = 0;
}
i = q ;
do{
i = i - 1;
} while (i >= 0 && (k1 < queries[i].l || k1 > queries[i].r));
if (i >= 0){
l = queries[i].l;
r = queries[i].r;
ign = i;
for (i = i-1; i >= 0; i--){
if (queries[i].r < l || queries[i].l > r){
queries[i].ignore = 1;
}
else{
if (queries[i].r > r && queries[i].l >= l)
r = queries[i].r;
else if (queries[i].l < l && queries[i].r <= r)
l = queries[i].l;
else if (queries[i].l < l && queries[i].r > r){
ign = i;
r = queries[i].r;
l = queries[i].l;
}
}
}
l = 0;
r = 0;
si = 0;
for (i = 0; i <= ign; i++){
if (!queries[i].ignore){
for (sj = si - 1; sj >= 0; sj--){
if (sarea[sj].l < queries[i].l && queries[i].l < sarea[sj].r) break;
if (sarea[sj].l < queries[i].r && queries[i].r < sarea[sj].r) break;
if (sarea[sj].l >= queries[i].l && queries[i].r >= sarea[sj].r) break;
}
if (sj == -1){
qsort(a + queries[i].l, queries[i].r - queries[i].l + 1, sizeof(int), cmp);
sarea[si] = queries[i];
si++;
}
else{
changed =0;
l = sarea[sj].l;
r = sarea[sj].r;
if (queries[i].l < l){
changed=1;
hr = l - queries[i].l;
memcpy(b, a + queries[i].l, hr*sizeof(int));
//qsort(b, hr, sizeof(int), cmp);
insertionsort(b,hr);
mi = 0;
j = l;
k = queries[i].l;
nr = (r < queries[i].r ? r : queries[i].r);
while (mi < hr && j <= nr)
{
a[k++] = (b[mi] < a[j] ? b[mi++] : a[j++]);
}
while (mi < hr) a[k++] = b[mi++];
}
if (queries[i].r > r){
changed+=2;
hr = queries[i].r - r;
memcpy(b, a + r + 1, hr*sizeof(int));
//qsort(b, hr, sizeof(int), cmp);
insertionsort(b,hr);
mi = hr - 1;
j = r;
k = queries[i].r;
while (mi >= 0 && j >= queries[i].l)
{
a[k--] = (b[mi] > a[j] ? b[mi--] : a[j--]);
}
while (mi >= 0) a[k--] = b[mi--];
r = queries[i].r;
}
if (changed){
sarea[sj].l = queries[i].l;
sarea[sj].r = queries[i].r;
}
}
}
}
}
printf("%d", a[k1]);
return 0;
}
Leave a comment below
