CollegeStash

Items in Container

Written by

Shiva Charan Devabhaktuni

An inventory management system represents items and compartment walls as a string s:

  • * represents an item.
  • ​| represents a compartment wall (pipe).​

An item is considered enclosed (inside a valid compartment) only if it lies between two compartment walls (|…|). Items outside the outermost walls within a specified substring range are excluded.​ Given a string s and two integer arrays startIndices and endIndices, determine the number of enclosed items for each range [startIndices[i], endIndices[i]].​

Complete the function getItems:

function getItems(
  s: string,
  startIndices: number[],
  endIndices: number[]
): number[]

Solution

const getItems = (str, startIndices, endIndices) => {
  const n = str.length;
  const prefix = new Array(n).fill(0);
  const leftPipe = new Array(n).fill(-1);
  const rightPipe = new Array(n).fill(-1);

  // 1. Compute prefix sum of '*' and nearest left pipe
  let count = 0;
  let lastLeftPipe = -1;
  for (let i = 0; i < n; i++) {
    if (str[i] === '*') {
      count++;
    } else {
      lastLeftPipe = i;
    }
    prefix[i] = count;
    leftPipe[i] = lastLeftPipe;
  }

  // 2. Compute nearest right pipe
  let lastRightPipe = -1;
  for (let i = n - 1; i >= 0; i--) {
    if (str[i] === '|') {
      lastRightPipe = i;
    }
    rightPipe[i] = lastRightPipe;
  }

  // 3. Process 1-indexed queries
  const result = [];
  for (let i = 0; i < startIndices.length; i++) {
    const start = startIndices[i] - 1;
    const end = endIndices[i] - 1;

    const firstPipe = rightPipe[start];
    const lastPipe = leftPipe[end];

    // Valid container requires two distinct pipes where firstPipe < lastPipe
    if (firstPipe !== -1 && lastPipe !== -1 && firstPipe < lastPipe) {
      result.push(prefix[lastPipe] - prefix[firstPipe]);
    } else {
      result.push(0);
    }
  }

  return result;
};

// Test Case
console.log(getItems('|**|*|*', [1, 1], [5, 6])); // Output: [2, 3]

Complexity

  • ​Time Complexity: O(N + Q) — O(N) preprocessing across the string of length N, followed by O(1) per query for Q queries.​
  • Space Complexity: O(N) for the lookup tables.

More posts