Frontend School

Find Valid Pickup Sequences

DSA
easy

Find Valid Pickup Sequences

Easy
Backtracking
Arrays
Permutations

Overview

In Zepto's fast-paced delivery environment, efficiently grouping items for pickup is crucial. To optimize delivery routes and batching, we sometimes need to explore all possible ways to combine a specific number of items for a single trip. This ensures flexibility in dispatching and helps identify optimal pickup strategies.

What you need to do / Task

You are given a list of N distinct items, each identified by a unique integer. Your task is to implement a function findPickupSequences that generates all unique ordered sequences of exactly k items that can be picked from the given list.

Input & output

  • items: An array of distinct integers representing the available items.
  • k: An integer representing the exact number of items to be picked in each sequence.
  • Return: A 2D array (list of lists) where each inner array represents a unique ordered sequence of k items. The order of sequences in the outer array does not matter.

Clarifications

  • All items in the items array are distinct.
  • The order of items within a sequence matters (e.g., [1, 2] is different from [2, 1]).
  • Each item can be used at most once in a single sequence.
  • If k is 0, return [[]] (a single empty sequence).
  • If k > items.length, no valid sequences can be formed, so return [].

Examples

1

Example 1

Input:

items = [1, 2, 3], k = 2

Output:

[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

Note:

From items [1, 2, 3], we need to pick exactly 2 items. The unique ordered sequences are [1,2], [1,3], [2,1], [2,3], [3,1], and [3,2].

2

Example 2

Input:

items = [7, 8], k = 1

Output:

[[7], [8]]

Note:

From items [7, 8], we need to pick exactly 1 item. The unique ordered sequences are [7] and [8].

3

Example 3

Input:

items = [5], k = 0

Output:

[[]]

Note:

When k is 0, the only valid sequence is an empty one.

4

Example 4

Input:

items = [1, 2], k = 3

Output:

[]

Note:

It's impossible to pick 3 items from a list of 2 items, so no sequences are returned.

Constraints

Constraints & assumptions

  • 1 <= items.length <= 8
  • 0 <= k <= items.length
  • 0 <= items[i] <= 100
  • The items array contains distinct integers.

Out of scope

  • Optimizing for the "best" sequence (e.g., shortest path, highest value).
  • Handling non-distinct items (assume all items are unique).
  • Concurrency or distributed processing of sequences.

What interviewers evaluate

  • Correctly implements a backtracking algorithm to explore all valid sequences.
  • Handles edge cases such as k=0 or k > items.length.
  • Ensures that each item is used at most once within a sequence.
  • Produces unique ordered sequences without duplicates.

Loading editor...