Array Index Shift — Problem Statement & Solution Guide
Problem Description
You are given a lineup of n distinct groups on a linear stage. The i‑th group is identified by a unique name names[i] and currently occupies position pos[i] (an integer). All positions are distinct and lie within the non‑negative integer line. Some positions on the stage are empty because the maximum occupied position may be larger than n‑1. A group that is not already at the first position (position 0) may move left to any empty slot that lies strictly between the last occupied position of any earlier group and its own current position. After such a move the relative order of all groups (by their original index in names) must remain strictly increasing. Determine, in the original order, all group names that can be shifted left under these rules. Output the qualifying names separated by a single space; if none exist output the word "None".
Input:
- An integer n (1 ≤ n ≤ 10⁵).
- A line with n space‑separated distinct strings names[i] (each length ≤ 20).
- A line with n space‑separated distinct integers pos[i] (0 ≤ pos[i] ≤ 10⁹).
Output:
- A single line containing the eligible group names in their original order, separated by spaces, or the word "None" if no group can be moved.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Array Index Shift"
WHY DOES IT MATTER?
Index compression appears in memory layout optimizations, coordinate compression in geometry, and rank‑based queries; mastering it prevents hidden quadratic blow‑ups when dealing with sparse identifiers.
OPTIMIZATION CHALLENGE
The key insight is that the final position of each group depends only on how many groups are before it, i.e., its rank, not on the exact size of gaps, allowing a single sort to replace many incremental moves.
REAL-WORLD CONNECTION
Think of a warehouse where pallets are placed on numbered shelves with gaps; to maximize space you slide all pallets to the front while keeping their loading order, analogous to compressing array indices.
During an interview, first state the rank‑compression idea, then choose the simplest implementation—sorting plus a hashmap for O(n log n) time—unless the constraints explicitly favor linear counting sort.
COMPLEXITY AT A GLANCE
O(n log n)O(n)Core Theory — Why This Approach?
The problem reduces to a stable ordering compression of sparse indices. By sorting groups by their current position we obtain the exact relative order they appear on the stage. Once ordered, we can re‑assign consecutive positions starting from zero, which is equivalent to applying a rank transformation to the original positions. A naïve simulation that moves each group one step at a time would be O(n × maxPos) and quickly exceeds limits when the stage is large. The optimal paradigm leverages sorting (or counting sort when positions are bounded) to compute each element’s rank in O(n log n) time, then writes the new compacted positions in a single linear pass, achieving O(n) additional space.
Interview Questions on This Problem
Q1How would you compress a list of distinct, non‑contiguous integer indices into a dense 0‑based range while preserving original order?
Sort the items by their original index, then iterate assigning new indices 0,1,2,… in that order; finally map the new indices back to the original identifiers.
Q2If the maximum original position is at most 10⁶, can you improve the O(n log n) solution?
Yes—use counting sort or a boolean bucket array of size maxPos+1 to record occupied slots, then scan the bucket to assign new positions in O(maxPos) time, which is linear when maxPos is O(n).
Q3Explain why a two‑pointer in‑place shift (moving each element left until it hits a filled slot) fails for large gaps.
Each shift may traverse many empty slots, leading to O(n × gap) operations; in the worst case with a single element at position n‑1, the algorithm performs O(n²) moves, which is unacceptable for n up to 10⁵ or more.
Examples
Input
5 A B C D E 0 2 4 5 7
Output
B C E
Explanation: Empty slots are positions 1,3,6. - B (pos 2) has an empty slot 1 between the previous max position 0 and 2 → eligible. - C (pos 4) has empty slot 3 between previous max 2 and 4 → eligible. - D (pos 5) has no empty slot between previous max 4 and 5 → not eligible. - E (pos 7) has empty slot 6 between previous max 5 and 7 → eligible. Result: B C E.
Input
4 X Y Z W 0 1 2 3
Output
None
Explanation: All positions 0‑3 are occupied; there is no empty slot before any group other than the first, so no group can shift left.
Input
6 G1 G2 G3 G4 G5 G6 0 3 4 6 9 10
Output
G2 G4 G5
Explanation: Stage positions up to 10 give empty slots 1,2,5,7,8. - G2 (pos 3) sees empty slots 1,2 after previous max 0 → eligible. - G3 (pos 4) has no empty slot between previous max 3 and 4 → not eligible. - G4 (pos 6) has empty slot 5 after previous max 4 → eligible. - G5 (pos 9) has empty slots 7,8 after previous max 6 → eligible. - G6 (pos 10) has no empty slot after previous max 9 → not eligible. Result: G2 G4 G5.
Constraints
- 1 <= n <= 100000
- All names are distinct strings of length <= 20
- All pos[i] are distinct integers with 0 <= pos[i] <= 10^9
- The stage length is defined as max(pos) + 1, allowing empty slots between occupied positions
Optimal Approach & Strategy
Sort groups by current position, then in one pass assign consecutive new positions starting from zero.
Brute Force Approach
Repeatedly move each group one step left until it reaches the first empty slot, updating positions after every move.
Verified Code Solutions
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/);
let idx=0;
function getShiftedGroups(n, names, pos){
const pairs = [];
for(let i=0;i<n;i++) pairs.push({p:pos[i], name:names[i]});
pairs.sort((a,b)=>a.p-b.p);
const ans=[];
for(let i=1;i<n;i++){
if(pairs[i].p !== pairs[i-1].p + 1) ans.push(pairs[i].name);
}
return ans;
}
if(input.length===0){process.exit(0);}
const n = parseInt(input[idx++]);
const names = [];
for(let i=0;i<n;i++) names.push(input[idx++]);
const pos = [];
for(let i=0;i<n;i++) pos.push(parseInt(input[idx++]));
const res = getShiftedGroups(n,names,pos);
console.log(res.join(' '));#include <bits/stdc++.h>
using namespace std;
vector<string> getShiftedGroups(int n, const vector<string>& names, const vector<int>& pos) {
vector<pair<int,string>> vp;
vp.reserve(n);
for(int i=0;i<n;i++) vp.emplace_back(pos[i], names[i]);
sort(vp.begin(), vp.end(), [](const auto& a, const auto& b){return a.first<b.first;});
vector<string> ans;
for(int i=1;i<n;i++){
if(vp[i].first != vp[i-1].first + 1) ans.push_back(vp[i].second);
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<string> names(n); for(int i=0;i<n;i++) cin>>names[i];
vector<int> pos(n); for(int i=0;i<n;i++) cin>>pos[i];
vector<string> res = getShiftedGroups(n,names,pos);
for(size_t i=0;i<res.size();i++){
if(i) cout<<' ';
cout<<res[i];
}
cout<<"\n";
return 0;
}import java.io.*;
import java.util.*;
public class Main {
private static List<String> getShiftedGroups(int n, List<String> names, List<Integer> pos) {
List<Pair> list = new ArrayList<>();
for(int i=0;i<n;i++) list.add(new Pair(pos.get(i), names.get(i)));
list.sort(Comparator.comparingInt(p->p.position));
List<String> ans = new ArrayList<>();
for(int i=1;i<n;i++){
if(list.get(i).position != list.get(i-1).position + 1){
ans.add(list.get(i).name);
}
}
return ans;
}
private static class Pair{
int position; String name;
Pair(int p, String n){position=p; name=n;}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if(line==null||line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
String[] nameTokens = br.readLine().trim().split(" ");
List<String> names = Arrays.asList(nameTokens);
String[] posTokens = br.readLine().trim().split(" ");
List<Integer> pos = new ArrayList<>();
for(String s: posTokens) pos.add(Integer.parseInt(s));
List<String> res = getShiftedGroups(n, names, pos);
System.out.println(String.join(" ", res));
}
}import sys
def get_shifted_groups(n, names, pos):
pairs = list(zip(pos, names))
pairs.sort(key=lambda x: x[0])
ans = []
for i in range(1, n):
if pairs[i][0] != pairs[i-1][0] + 1:
ans.append(pairs[i][1])
return ans
def main():
data = sys.stdin.read().strip().split()
if not data:
return
it = iter(data)
n = int(next(it))
names = [next(it) for _ in range(n)]
pos = [int(next(it)) for _ in range(n)]
res = get_shifted_groups(n, names, pos)
print(' '.join(res))
if __name__ == "__main__":
main()
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/);
let idx=0;
function getShiftedGroups(n, names, pos){
const pairs = [];
for(let i=0;i<n;i++) pairs.push({p:pos[i], name:names[i]});
pairs.sort((a,b)=>a.p-b.p);
const ans=[];
for(let i=1;i<n;i++){
if(pairs[i].p !== pairs[i-1].p + 1) ans.push(pairs[i].name);
}
return ans;
}
if(input.length===0){process.exit(0);}
const n = parseInt(input[idx++]);
const names = [];
for(let i=0;i<n;i++) names.push(input[idx++]);
const pos = [];
for(let i=0;i<n;i++) pos.push(parseInt(input[idx++]));
const res = getShiftedGroups(n,names,pos);
console.log(res.join(' '));Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.