Solved a Leetcode Coding Question

Inspiration

This project was inspired by my commitment to sharpening my algorithmic skills, specifically in handling data retrieval and optimization challenges commonly found in coding interviews. The problem required a unique approach to quickly find the maximum beauty of items within a specified price range, which has practical implications for resource-constrained searching.

Approach & Implementation

I used a two-step approach to build the solution:

1. Sorting and Preprocessing: To efficiently search for the maximum beauty of items up to a given price, I first sorted the items based on their price. This allowed me to preprocess the data for efficient querying by building an array that accumulates the maximum beauty values up to each price point.
2. Binary Search for Queries: Leveraging the sorted array, I used binary search to quickly find the highest possible beauty within the budget specified in each query. This approach ensures we maintain optimal performance even as the dataset grows.

Challenges Faced

One of the main challenges was handling the time complexity to ensure it stayed within acceptable limits. Initial brute-force approaches resulted in timeouts, especially with larger datasets. Optimizing with sorting and binary search significantly reduced the runtime complexity, making the solution scalable. Additionally, handling edge cases, such as queries with prices lower than any item's price, required careful implementation to avoid errors.

Lessons Learned

Through this project, I deepened my understanding of binary search, sorting algorithms, and optimization strategies. This experience reinforced the importance of preprocessing data for efficiency, as well as the power of binary search in reducing query time for large datasets.

Key Technologies & Tools

• Programming Language: Java
• Algorithms Used: Sorting, Binary Search

Code Solution

class Solution { public int[] maximumBeauty(int[][] items, int[] queries) { Arrays.sort(items, (a, b) -> { if(a[0] == b[0]) return a[1] - b[1]; return a[0] - b[0]; });

    int n = items.length;
    int maxBeauty[] = new int[n];
    maxBeauty[0] = items[0][1];

    for(int i = 1; i < n; i++){
        maxBeauty[i] = Math.max(maxBeauty[i - 1], items[i][1]);
    }

    int ans[] = new int[queries.length];
    for(int i = 0; i < queries.length; i++){
        int query = queries[i];
        int left = 0, right = n- 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(items[mid][0] <= query)
            left = mid + 1;
            else
            right = mid - 1;
        }
        ans[i] = right >= 0 ? maxBeauty[right] : 0;
    }
    return ans;
}

}

Built With

• algorithms
• datastructures
• java