Frontend School

Optimal Production Segment

DSA
hard

Optimal Production Segment

Hard
Two Pointers
Sliding Window
Arrays
Greedy

Overview

At Lenskart, ensuring consistent quality and diversity in lens production batches is crucial. We produce various lens types, each with an associated quality score. To optimize our production lines and perform quality checks, we need to identify specific segments of our production sequence that meet stringent criteria for both type distribution and average quality.

What you need to do / Task

Implement a function findOptimalProductionSegment that takes a sequence of lenses, required counts for two specific lens types, and a minimum average quality threshold. Your function should identify the shortest continuous segment of lenses that satisfies all the following conditions:

  1. It contains at least k_type1 lenses of type1_char.
  2. It contains at least k_type2 lenses of type2_char.
  3. The average quality score of all lenses within the segment must be greater than or equal to min_avg_quality.

If multiple such shortest segments exist, return the one that appears earliest in the overall sequence. If no segment satisfies all conditions, return [-1, -1].

Input & output

  • lenses: An array of arrays, where each inner array [quality, type_char] represents a lens. quality is a number (integer), and type_char is a string (single character, e.g., 'A', 'B', 'C').
  • k_type1: A number representing the minimum required count for type1_char.
  • type1_char: A string (single character) representing the first specific lens type.
  • k_type2: A number representing the minimum required count for type2_char.
  • type2_char: A string (single character) representing the second specific lens type.
  • min_avg_quality: A number representing the minimum acceptable average quality score for the segment.

Returns: An array [start_index, end_index] (both 0-indexed, inclusive) representing the start and end indices of the optimal segment. Returns [-1, -1] if no such segment exists.

Clarifications

  • The lenses array can be empty. If so, return [-1, -1].
  • Quality scores are non-negative integers.
  • k_type1 and k_type2 will be non-negative integers.
  • min_avg_quality will be a non-negative number.
  • type1_char and type2_char will be distinct single characters.

Examples

1

Example 1

Input:

lenses = [[80, "A"], [90, "B"], [70, "A"], [95, "C"], [85, "B"], [60, "A"]], k_type1 = 2, type1_char = "A", k_type2 = 2, type2_char = "B", min_avg_quality = 80

Output:

[0,4]

Note:

The segment from index 0 to 4 is [[80, "A"], [90, "B"], [70, "A"], [95, "C"], [85, "B"]]. It contains 2 'A's and 2 'B's. The sum of qualities is 80+90+70+95+85 = 420. Average quality is 420/5 = 84, which is >= 80. Its length is 5. Another valid segment is [1,5] (length 5) but [0,4] appears earlier, so it is preferred.

2

Example 2

Input:

lenses = [[50, "A"], [60, "C"], [70, "B"]], k_type1 = 2, type1_char = "A", k_type2 = 1, type2_char = "B", min_avg_quality = 60

Output:

[-1,-1]

Note:

No segment in the given sequence contains at least 2 'A' type lenses, so no valid segment can be found.

3

Example 3

Input:

lenses = [[100, "A"], [100, "B"], [90, "A"], [90, "B"]], k_type1 = 2, type1_char = "A", k_type2 = 2, type2_char = "B", min_avg_quality = 95

Output:

[0,3]

Note:

The segment from index 0 to 3, which is the entire array [[100, "A"], [100, "B"], [90, "A"], [90, "B"]], contains 2 'A's and 2 'B's. The sum of qualities is 100+100+90+90 = 380. Average quality is 380/4 = 95, which is >= 95. This is the shortest and only valid segment.

Constraints

Constraints & assumptions

  • 1 <= lenses.length <= 10^5
  • 0 <= lenses[i][0] (quality) <= 100
  • lenses[i][1] will be an uppercase English letter (e.g., 'A', 'B', 'C').
  • 0 <= k_type1, k_type2 <= lenses.length
  • 0 <= min_avg_quality <= 100
  • type1_char and type2_char will be distinct single characters.
  • Time complexity: O(N) where N is lenses.length.
  • Space complexity: O(1) beyond input storage.

Out of scope

  • Error handling for invalid input types or formats (assume valid inputs as per constraints).
  • Handling floating-point precision issues beyond standard comparisons.

What interviewers evaluate

  • Correctness: The solution correctly identifies the shortest valid segment and handles edge cases.
  • Algorithm Design: Efficient use of the Two Pointers (sliding window) technique to achieve O(N) time complexity.
  • Code Structure & Readability: Clean, well-organized, and understandable code.
  • Edge Case Handling: Proper handling of empty inputs, no valid segments, or segments at array boundaries.

Loading editor...