BackmediumArraysAccenture

Array Index Shift Solution

Problem Statement

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.
Example 1
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.

Example 2
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.

Example 3
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
Live Compiler1 Free Run Available
Loading Editor...
Test Cases & Output
Click "Run" to test your 1 free compile trial!

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free

Array Index Shift — Problem Statement & Solution Guide

ArraysMediumNEW OR EXISTING ID
TimeO(n log n)
|
SpaceO(n)

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"

medium

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

⏱ Time:O(n log n)
💾 Space: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

Example 1

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.

Example 2

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.

Example 3

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

JavaScript Solution
Time: O(n log n)
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

Accenture

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.