Frontend School

Longest Balanced Item Subarray

DSA
medium

Longest Balanced Item Subarray

Medium
Hashing
Arrays
Prefix Sum

Overview

At Swiggy, understanding customer order patterns is crucial for optimizing logistics, inventory, and personalized recommendations. One interesting metric is identifying 'balanced' segments within an order, where the presence of two specific item types is equal. This problem challenges you to find the longest contiguous sequence of items in a customer's order that maintains this balance.

What you need to do / Task

Implement a function findLongestBalancedItemSubarray that takes an array of item IDs (itemIds), and two distinct specific item IDs (itemX, itemY). Your task is to return the length of the longest contiguous subarray within itemIds where the total count of itemX is exactly equal to the total count of itemY.

Input & output

  • itemIds: A number[] representing a sequence of item IDs in a customer's order.
  • itemX: A number representing the ID of the first specific item to balance.
  • itemY: A number representing the ID of the second specific item to balance.
  • Return: A number representing the length of the longest contiguous subarray where count(itemX) == count(itemY). If no such non-empty subarray exists, return 0.

Clarifications

  • itemX and itemY are guaranteed to be distinct (i.e., itemX != itemY).
  • If itemIds is empty, the result should be 0.
  • Item IDs can be large numbers, but their values only matter for equality comparison.

Examples

1

Example 1

Input:

itemIds = [1, 2, 1, 3, 2, 1], itemX = 1, itemY = 2

Output:

5

Note:

The subarray [1, 2, 1, 3, 2] has two 1s and two 2s (length 5). The subarray [1, 2] has one 1 and one 2 (length 2). The subarray [2, 1] has one 2 and one 1 (length 2). The longest balanced subarray is [1, 2, 1, 3, 2].

2

Example 2

Input:

itemIds = [5, 5, 5, 5], itemX = 5, itemY = 10

Output:

0

Note:

No itemY (10) is present in the array. For any non-empty subarray, the count of 5 will be greater than 0, while the count of 10 will be 0. Thus, no non-empty subarray can be balanced.

3

Example 3

Input:

itemIds = [10, 20, 10, 20, 10, 20], itemX = 10, itemY = 20

Output:

6

Note:

The entire array [10, 20, 10, 20, 10, 20] has three 10s and three 20s, making it balanced with a length of 6. This is the longest possible.

Constraints

Constraints & assumptions

  • 1 <= itemIds.length <= 10^5
  • 0 <= itemIds[i] <= 10^9 (item IDs can be large, but are non-negative integers)
  • 0 <= itemX, itemY <= 10^9
  • itemX != itemY

Out of scope

  • Handling invalid input types (e.g., itemIds not being an array, or itemX/itemY not being numbers).
  • Optimizing for memory beyond standard hash map usage for O(N) space complexity.

What interviewers evaluate

  • Correctness: The solution must correctly identify the longest balanced subarray for all valid inputs, including edge cases (e.g., no itemX or itemY present, no balanced subarrays).
  • Efficiency: The algorithm should be optimal in terms of time and space complexity for the given constraints.
  • Clarity: The code should be clean, readable, and well-structured, demonstrating good coding practices.
  • Problem-solving: Ability to break down the problem, identify the underlying algorithmic pattern, and articulate the thought process.

Loading editor...