Frontend School

Find Product Insertion Point

DSA
easy

Find Product Insertion Point

Easy
Binary Search
Arrays

Overview

At Flipkart, maintaining a vast product catalog requires efficient data management. When new products are added or existing ones are re-priced, it's crucial to quickly determine their correct position to maintain sorted order. This allows for faster searching, indexing, and overall catalog management. This problem focuses on efficiently locating where a new product's price would fit into an already sorted list of product prices.

What you need to do / Task

  1. Implement a function findInsertionPoint that takes a sorted array of product prices (prices) and a targetPrice as input.
  2. The function should return the index where the targetPrice should be inserted to maintain the ascending sorted order of the prices array.
  3. If the targetPrice is already present, return the index of its first occurrence.
  4. If the targetPrice is greater than all existing prices, return prices.length.

Input & output

  • Input:
    • prices: An array of numbers (number[]), representing product prices, sorted in non-decreasing order.
    • targetPrice: A number (number), representing the price of the new product.
  • Output:
    • A number (number), representing the index where targetPrice should be inserted.

Clarifications

  • An empty prices array should result in an insertion point of 0.
  • The prices array can contain duplicate values.
  • All prices (in prices and targetPrice) are non-negative integers.

Examples

1

Example 1

Input:

prices = [10, 20, 30, 40], targetPrice = 25

Output:

2

Note:

25 should be inserted between 20 (index 1) and 30 (index 2).

2

Example 2

Input:

prices = [10, 20, 30, 40], targetPrice = 10

Output:

0

Note:

10 is already present at index 0. We return the index of its first occurrence.

3

Example 3

Input:

prices = [10, 20, 20, 30, 40], targetPrice = 20

Output:

1

Note:

20 is present multiple times. The first occurrence is at index 1.

4

Example 4

Input:

prices = [10, 20, 30], targetPrice = 50

Output:

3

Note:

50 is greater than all existing prices, so it should be inserted at the end (index 3).

5

Example 5

Input:

prices = [], targetPrice = 100

Output:

0

Note:

An empty array, 100 should be inserted at index 0.

Constraints

Constraints & assumptions

  • 0 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^9
  • 0 <= targetPrice <= 10^9
  • The prices array is always sorted in non-decreasing order.

Out of scope

  • Modifying the input prices array.
  • Handling non-numeric or negative price inputs; assume valid inputs per constraints.

What interviewers evaluate

  • Correctness: The solution correctly identifies the insertion point for all valid inputs and edge cases (empty array, target at ends, duplicates).
  • Efficiency: The solution achieves an optimal time complexity, ideally logarithmic with respect to the array size.
  • Code Quality: The code is well-structured, readable, and uses appropriate variable names.
  • Problem-Solving Approach: Candidate demonstrates a clear understanding of binary search and applies it effectively.

Loading editor...