Ecommerce Product Recommendation — Problem Statement & Solution Guide

ArraysMediumGeneral

TimeO(n)

SpaceO(1)

Problem Description

You are tasked with implementing a product selection algorithm for an e-commerce platform. The system receives a list of available items, where each item is represented by a pair of integers: [rating, price]. The rating indicates the quality score (higher is better), and the price is the cost in currency units.

Given a maximum budget constraint, identify the single product that offers the highest rating among all items whose price does not exceed the budget. If multiple products share the same highest rating within the budget, return the one with the lowest price. If no product fits within the budget, return -1.

The function should efficiently process the list to determine the optimal choice based on the specified criteria.

DSA Pattern Breakdown

"Ecommerce Product Recommendation"

medium

WHY DOES IT MATTER?

Selecting the optimal element under a single numeric constraint is a recurring pattern in interview problems because it tests a candidate’s ability to reduce a problem to a linear scan with constant‑space bookkeeping, avoiding unnecessary sorting or nested loops.

OPTIMIZATION CHALLENGE

The key insight is that the optimal product can be identified on‑the‑fly; you never need to store or sort the entire list, which collapses both time and space from O(n log n) or O(n^2) down to O(n) and O(1).

REAL-WORLD CONNECTION

E‑commerce recommendation engines constantly filter millions of SKUs against a user's budget and preferences, similar to how a load balancer routes requests to the best‑fit server based on capacity constraints.

During the interview, write the loop that updates a ‘best’ variable only when the current item satisfies the budget and improves the rating (or ties with a lower price); this concise pattern demonstrates clear thinking and avoids off‑by‑one bugs.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem reduces to a classic selection under a constraint: we must scan a list of items and pick the one with the maximum rating that does not exceed a given budget. A naïve solution would compare every pair of items, leading to O(n^2) time, which quickly becomes infeasible for large catalogs containing millions of products. The optimal paradigm leverages a single linear pass while maintaining the best candidate seen so far, achieving O(n) time and O(1) extra space. This approach works because the decision criterion (rating then price) is monotonic – once an item is discarded it can never become optimal later, so we never need to revisit earlier elements.

Interview Questions on This Problem

Q1How would you modify the solution if the requirement was to maximize rating * price ratio instead of rating alone?

Compute the ratio rating/price for each item that fits the budget, track the maximum ratio during a single pass, and return the corresponding product; the algorithmic complexity remains O(n) with O(1) space.

Q2What changes are needed if the budget constraint is a range [low, high] rather than a single upper bound?

During the linear scan, consider an item only if low ≤ price ≤ high; otherwise skip it. The rest of the logic stays identical, still O(n) time.

Q3Can you extend the algorithm to return the top‑k products within budget sorted by rating?

Maintain a min‑heap of size k while iterating; push qualifying items and pop when the heap exceeds k. This yields O(n log k) time and O(k) space, which is optimal for the top‑k variant.

Examples

Example 1

Input

products = [[4, 10], [5, 15], [3, 5], [5, 12]], budget = 12

Output

[5, 12]

Explanation: 1. Check [4, 10]: Price 10 <= 12. Candidate rating 4. 2. Check [5, 15]: Price 15 > 12. Skip. 3. Check [3, 5]: Price 5 <= 12. Candidate rating 3. 4. Check [5, 12]: Price 12 <= 12. Candidate rating 5. 5. Compare candidates: [4, 10] (rating 4), [3, 5] (rating 3), [5, 12] (rating 5). 6. Highest rating is 5. Only one product has this rating. 7. Return [5, 12].

Example 2

Input

products = [[8, 20], [8, 15], [9, 25]], budget = 20

Output

[8, 15]

Explanation: 1. Check [8, 20]: Price 20 <= 20. Candidate rating 8, price 20. 2. Check [8, 15]: Price 15 <= 20. Candidate rating 8, price 15. 3. Check [9, 25]: Price 25 > 20. Skip. 4. Candidates: [8, 20] and [8, 15]. 5. Both have the highest rating of 8. 6. Tie-breaker: Select the one with the lowest price. 15 < 20. 7. Return [8, 15].

Example 3

Input

products = [[2, 100], [1, 50]], budget = 10

Output

-1

Explanation: 1. Check [2, 100]: Price 100 > 10. Skip. 2. Check [1, 50]: Price 50 > 10. Skip. 3. No products fit within the budget. 4. Return -1.

Example 4

Input

products = [[10, 5], [10, 5], [9, 3]], budget = 5

Output

[10, 5]

Explanation: 1. Check [10, 5]: Price 5 <= 5. Candidate rating 10, price 5. 2. Check [10, 5]: Price 5 <= 5. Candidate rating 10, price 5. 3. Check [9, 3]: Price 3 <= 5. Candidate rating 9, price 3. 4. Candidates: [10, 5], [10, 5], [9, 3]. 5. Highest rating is 10. 6. Two products have rating 10. Both have price 5. 7. Return the first encountered or any valid instance: [10, 5].

Constraints

1 <= products.length <= 10^5
1 <= products[i][0] <= 10^9 (rating)
1 <= products[i][1] <= 10^9 (price)
1 <= budget <= 10^9

Optimal Approach & Strategy

Perform a single linear scan while maintaining the best qualifying product, achieving linear time and constant extra space.

Brute Force Approach

Check every possible pair of items to see which one beats the other under the budget, resulting in quadratic time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function findBestProduct(products, budget) {
    if (!products || products.length === 0) {
        return [];
    }
    
    let bestRating = -Infinity;
    let bestPrice = Infinity;
    let bestProduct = [];
    
    for (const product of products) {
        const [rating, price] = product;
        
        // Check if product is within budget
        if (price <= budget) {
            // Update if this product has a higher rating
            // or same rating but lower price
            if (rating > bestRating || (rating === bestRating && price < bestPrice)) {
                bestRating = rating;
                bestPrice = price;
                bestProduct = product;
            }
        }
    }
    
    return bestProduct;
}

// Example usage
const products = [[4, 10], [5, 15], [3, 5], [5, 12]];
const budget = 12;
const result = findBestProduct(products, budget);
console.log(result.length === 0 ? 'No product found' : `[${result[0]}, ${result[1]}]`);

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<int> findBestProduct(vector<vector<int>>& products, int budget) {
    if (products.empty()) {
        return {};
    }
    
    int bestRating = -1;
    int bestPrice = INT_MAX;
    vector<int> bestProduct;
    
    for (const auto& product : products) {
        int rating = product[0];
        int price = product[1];
        
        // Check if product is within budget
        if (price <= budget) {
            // Update if this product has a higher rating
            // or same rating but lower price
            if (rating > bestRating || (rating == bestRating && price < bestPrice)) {
                bestRating = rating;
                bestPrice = price;
                bestProduct = product;
            }
        }
    }
    
    return bestProduct;
}

int main() {
    vector<vector<int>> products = {{4, 10}, {5, 15}, {3, 5}, {5, 12}};
    int budget = 12;
    
    vector<int> result = findBestProduct(products, budget);
    
    if (result.empty()) {
        cout << "No product found" << endl;
    } else {
        cout << "[" << result[0] << ", " << result[1] << "]" << endl;
    }
    
    return 0;
}

import java.util.List;
import java.util.ArrayList;

public class Solution {
    public static List<Integer> findBestProduct(List<List<Integer>> products, int budget) {
        if (products == null || products.isEmpty()) {
            return new ArrayList<>();
        }
        
        int bestRating = Integer.MIN_VALUE;
        int bestPrice = Integer.MAX_VALUE;
        List<Integer> bestProduct = new ArrayList<>();
        
        for (List<Integer> product : products) {
            int rating = product.get(0);
            int price = product.get(1);
            
            // Check if product is within budget
            if (price <= budget) {
                // Update if this product has a higher rating
                // or same rating but lower price
                if (rating > bestRating || (rating == bestRating && price < bestPrice)) {
                    bestRating = rating;
                    bestPrice = price;
                    bestProduct = new ArrayList<>(product);
                }
            }
        }
        
        return bestProduct;
    }
    
    public static void main(String[] args) {
        List<List<Integer>> products = new ArrayList<>();
        products.add(List.of(4, 10));
        products.add(List.of(5, 15));
        products.add(List.of(3, 5));
        products.add(List.of(5, 12));
        int budget = 12;
        
        List<Integer> result = findBestProduct(products, budget);
        if (result.isEmpty()) {
            System.out.println("No product found");
        } else {
            System.out.println("[" + result.get(0) + ", " + result.get(1) + "]");
        }
    }
}

from typing import List

def find_best_product(products: List[List[int]], budget: int) -> List[int]:
    if not products:
        return []
    
    best_rating = float('-inf')
    best_price = float('inf')
    best_product = []
    
    for product in products:
        rating, price = product
        
        # Check if product is within budget
        if price <= budget:
            # Update if this product has a higher rating
            # or same rating but lower price
            if rating > best_rating or (rating == best_rating and price < best_price):
                best_rating = rating
                best_price = price
                best_product = product
    
    return best_product

# Example usage
if __name__ == "__main__":
    products = [[4, 10], [5, 15], [3, 5], [5, 12]]
    budget = 12
    result = find_best_product(products, budget)
    print(f"[{result[0]}, {result[1]}]" if result else "No product found")

function findBestProduct(products, budget) {
    if (!products || products.length === 0) {
        return [];
    }
    
    let bestRating = -Infinity;
    let bestPrice = Infinity;
    let bestProduct = [];
    
    for (const product of products) {
        const [rating, price] = product;
        
        // Check if product is within budget
        if (price <= budget) {
            // Update if this product has a higher rating
            // or same rating but lower price
            if (rating > bestRating || (rating === bestRating && price < bestPrice)) {
                bestRating = rating;
                bestPrice = price;
                bestProduct = product;
            }
        }
    }
    
    return bestProduct;
}

// Example usage
const products = [[4, 10], [5, 15], [3, 5], [5, 12]];
const budget = 12;
const result = findBestProduct(products, budget);
console.log(result.length === 0 ? 'No product found' : `[${result[0]}, ${result[1]}]`);

Asked in Top Tech Interviews

PhonePe

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Ecommerce Product Recommendation Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Ecommerce Product Recommendation — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor