Frontend School

Optimal Material Blend

DSA
medium

Optimal Material Blend

Medium
Two Pointers
Sorting
Arrays

Overview

Livspace designers meticulously select materials for their projects, balancing aesthetics with practical requirements like durability. For certain custom composite elements, two base materials are blended. The combined durability of these blended materials is simply the sum of their individual durability scores. To meet precise engineering specifications, it's crucial to identify two available materials whose combined durability score is as close as possible to a predetermined targetDurability.

What you need to do / Task

Your task is to implement a function findOptimalMaterialBlend that takes an array of durabilityScores for available materials and a targetDurability as input. The function should identify two distinct materials (i.e., from different original positions in the input array) whose sum of scores has the minimum absolute difference from the targetDurability.

Deliverables:

  1. Return the 0-based original indices of the two chosen materials.
  2. If multiple pairs yield the same minimum absolute difference, prioritize the pair where the smaller of the two original indices is minimized.
  3. If the smaller original indices are identical, then prioritize the pair with the smaller larger original index. (Effectively, a lexicographical comparison of the sorted index pair [min(idx1, idx2), max(idx1, idx2)]).
  4. The returned array [index1, index2] must always have index1 < index2.

Input & output

Function Signature:

function findOptimalMaterialBlend(durabilityScores: number[], targetDurability: number): number[]

Input Parameters:

  • durabilityScores: An array of numbers, where durabilityScores[i] represents the durability score of the i-th material.
  • targetDurability: A number representing the desired total durability score.

Return Value:

  • An array number[] of length 2, [index1, index2], representing the 0-based original indices of the two materials that form the optimal blend. index1 will always be less than index2.

Examples

1

Example 1

Input:

durabilityScores = [10, 20, 30, 40], targetDurability = 55

Output:

[0, 3]

Note:

Original indices: 10(0), 20(1), 30(2), 40(3). Sorted (score, original_index) pairs: [(10,0), (20,1), (30,2), (40,3)].

  • Pointers at (10,0) and (40,3). Sum = 50. Diff = |55-50|=5. Best so far: [0,3], diff=5.
  • Move left pointer (sum < target). Pointers at (20,1) and (40,3). Sum = 60. Diff = |55-60|=5. Current pair [1,3]. Compared to [0,3], [0,3] is preferred due to smaller first index (0 < 1).
  • Move right pointer (sum > target). Pointers at (20,1) and (30,2). Sum = 50. Diff = |55-50|=5. Current pair [1,2]. Compared to [0,3], [0,3] is preferred due to smaller first index (0 < 1).
  • Pointers cross. Final optimal blend is [0,3].
2

Example 2

Input:

durabilityScores = [5, 15, 25, 35], targetDurability = 30

Output:

[0, 2]

Note:

Original indices: 5(0), 15(1), 25(2), 35(3). Sorted (score, original_index) pairs: [(5,0), (15,1), (25,2), (35,3)].

  • Pointers at (5,0) and (35,3). Sum = 40. Diff = |30-40|=10. Best: [0,3], diff=10.
  • Move right pointer (sum > target). Pointers at (5,0) and (25,2). Sum = 30. Diff = |30-30|=0. Perfect match found! Return [0,2].
3

Example 3

Input:

durabilityScores = [100, 50, 200, 150], targetDurability = 270

Output:

[0, 3]

Note:

Original indices: 100(0), 50(1), 200(2), 150(3). Sorted (score, original_index) pairs: [(50,1), (100,0), (150,3), (200,2)].

  • Pointers at (50,1) and (200,2). Sum = 250. Diff = |270-250|=20. Best so far: [1,2], diff=20.
  • Move left pointer (sum < target). Pointers at (100,0) and (200,2). Sum = 300. Diff = |270-300|=30. Current diff (30) is worse than best (20). Move right pointer (sum > target).
  • Pointers at (100,0) and (150,3). Sum = 250. Diff = |270-250|=20. Current diff (20) equals best (20). Current pair indices (original): [0,3]. Best pair indices: [1,2]. Comparing [0,3] vs [1,2]: The first index of [0,3] is 0, which is smaller than the first index of [1,2] (which is 1). So, [0,3] becomes the new best pair.
  • Move left pointer (sum < target). Pointers cross. Final optimal blend is [0,3].

Constraints

Constraints & assumptions

  • 2 <= durabilityScores.length <= 10^5
  • 1 <= durabilityScores[i] <= 10^9
  • 1 <= targetDurability <= 2 * 10^9
  • All elements in durabilityScores are unique (no two materials have the same score).

What interviewers evaluate

  • Algorithm Selection: Correct application of Two Pointers after appropriate preprocessing (sorting).
  • Edge Cases & Tie-breaking: Correct handling of minimum difference, including the specified tie-breaking rules for indices.
  • Time & Space Complexity: Optimal solution within O(N log N) time and O(N) space complexities.
  • Code Quality: Readability, modularity, and correctness of the implementation.

Loading editor...