Frontend School

Efficient Package Priority Sorting

DSA
medium

Efficient Package Priority Sorting

Medium
Two Pointers
Arrays
In-place

Overview

At Delhivery, efficient package sorting is crucial for optimizing loading and delivery routes. To streamline operations, packages are categorized by handling priority. For certain truck loads, all 'Priority' packages must be grouped together at the beginning of the sequence, followed by 'Standard' packages. This ensures that high-priority items are handled first during loading and unloading, reducing potential delays and improving overall logistics efficiency.

What you need to do / Task

Implement a function sortPackagesByPriority that takes an array of strings, packagePriorities, representing the handling priority of various packages. The function should rearrange the array in-place such that all packages with the "Priority" type appear before all packages with the "Standard" type. The relative order within the "Priority" group or the "Standard" group does not matter.

Input & output

Function Signature:

function sortPackagesByPriority(packagePriorities: string[]): void

Input:

  • packagePriorities: An array of strings. Each string will be either "Priority" or "Standard".

Output:

  • The function should modify the packagePriorities array in-place. It does not need to return anything explicitly (void).

Clarifications

  • Empty Array: If packagePriorities is empty, the function should do nothing.
  • Case Sensitivity: Assume the input strings will strictly be "Priority" or "Standard" (capitalized as shown). No need to handle variations like "priority" or "STANDARD".
  • Only One Type: The array might contain only "Priority" packages or only "Standard" packages.

Examples

1

Example 1

Input:

packagePriorities = ["Standard", "Priority", "Standard", "Priority", "Standard"]

Output:

["Priority", "Priority", "Standard", "Standard", "Standard"]

Note:

All "Priority" packages are moved to the beginning of the array, and "Standard" packages to the end. The exact order within the "Priority" or "Standard" groups does not matter, as long as all "Priority" come before all "Standard".

2

Example 2

Input:

packagePriorities = ["Priority", "Priority", "Priority"]

Output:

["Priority", "Priority", "Priority"]

Note:

All packages are already "Priority", so the array remains unchanged as it already satisfies the condition.

3

Example 3

Input:

packagePriorities = ["Standard", "Standard", "Priority"]

Output:

["Priority", "Standard", "Standard"]

Note:

The single "Priority" package is moved to the front of the array to satisfy the grouping requirement.

4

Example 4

Input:

packagePriorities = []

Output:

[]

Note:

An empty input array results in an empty array, as there are no packages to sort.

Constraints

Constraints & assumptions

  • The length of packagePriorities array will be between 0 and 10^5.
  • Each element in packagePriorities will be one of two strings: "Priority" or "Standard".
  • The solution should modify the input array in-place.
  • Time complexity should be O(N), where N is the length of packagePriorities.
  • Space complexity should be O(1) (constant extra space).

Out of scope

  • Validation of input strings beyond "Priority" or "Standard".
  • Handling multiple other package types (e.g., "Fragile", "Heavy" alongside "Priority", "Standard"). The problem specifically deals with two distinct types.
  • Persistent storage or network operations.

What interviewers evaluate

  • Correctness: The final array must have all "Priority" elements preceding all "Standard" elements.
  • Efficiency: Solution must meet the O(N) time and O(1) space complexity requirements.
  • Edge Cases: Proper handling of empty arrays or arrays containing only one type of package.
  • Code Quality: Readability, maintainability, and proper use of the two-pointer technique.

Loading editor...