✅ Tutorial Video | Simple and Short | Working 12.11.2024
\n\nhttps://youtu.be/kybir7n8JJg?si=9bsPxiEvtf3d-YqM\n# #1 Sorting + Two Pointers - Most simple solution\n\n\n\npython3 []\nclass Solution:\n    def maximumBeau
\n\nhttps://youtu.be/kybir7n8JJg?si=9bsPxiEvtf3d-YqM\n# #1 Sorting + Two Pointers - Most simple solution\n\n\n\n```python3 []\nclass Solution:\n    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n        items.sort()  \n        queries = sorted([(q, i) for i, q in enumerate(queries)])  \n\n        res = [0] * len(queries)\n        max_bea = 0\n        j = 0\n        for q, i in queries:\n            while j < len(items) and items[j][0] <= q:\n                max_bea = max(max_bea, items[j][1])\n                j += 1\n\n            res[i] = max_bea\n\n        return res\n\n\n```\n```cpp []\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        sort(items.begin(), items.end());\n        vector<pair<int, int>> queriesWithIndex;\n        for (int i = 0; i < queries.size(); i++) {\n            queriesWithIndex.push_back({queries[i], i});\n        }\n        sort(queriesWithIndex.begin(), queriesWithIndex.end());\n        \n        vector<int> res(queries.size());\n        int maxBea = 0;\n        int j = 0;\n        for (auto [q, i] : queriesWithIndex) {\n            while (j < items.size() && items[j][0] <= q) {\n                maxBea = max(maxBea, items[j][1]);\n                j++;\n            }\n            res[i] = maxBea;\n        }\n        return res;\n    }\n};\n```\n```java []\nclass Solution {\n    public int[] maximumBeauty(int[][] items, int[] queries) {\n        Arrays.sort(items, (a, b) -> a[0] - b[0]);\n        int[][] queriesWithIndex = new int[queries.length][2];\n        for (int i = 0; i < queries.length; i++) {\n            queriesWithIndex[i] = new int[]{queries[i], i};\n        }\n        Arrays.sort(queriesWithIndex, (a, b) -> a[0] - b[0]);\n        \n        int[] res = new int[queries.length];\n        int maxBea = 0;\n        int j = 0;\n        for (int[] query : queriesWithIndex) {\n            while (j < items.length && items[j][0] <= query[0]) {\n                maxBea = Math.max(maxBea, items[j][1]);\n                j++;\n            }\n            res[query[1]] = maxBea;\n        }\n        return res;\n    }\n}\n```\n```csharp []\npublic class Solution {\n    public int[] MaximumBeauty(int[][] items, int[] queries) {\n        Array.Sort(items, (a, b) => a[0].CompareTo(b[0]));\n        var queriesWithIndex = queries.Select((q, i) => new { Query = q, Index = i })\n                                    .OrderBy(x => x.Query)\n                                    .ToArray();\n        \n        int[] res = new int[queries.Length];\n        int maxBea = 0;\n        int j = 0;\n        foreach (var query in queriesWithIndex) {\n            while (j < items.Length && items[j][0] <= query.Query) {\n                maxBea = Math.Max(maxBea, items[j][1]);\n                j++;\n            }\n            res[query.Index] = maxBea;\n        }\n        return res;\n    }\n}\n```\n```golang []\nfunc maximumBeauty(items [][]int, queries []int) []int {\n    sort.Slice(items, func(i, j int) bool {\n        return items[i][0] < items[j][0]\n    })\n    \n    type Query struct {\n        val, idx int\n    }\n    queriesWithIndex := make([]Query, len(queries))\n    for i, q := range queries {\n        queriesWithIndex[i] = Query{q, i}\n    }\n    sort.Slice(queriesWithIndex, func(i, j int) bool {\n        return queriesWithIndex[i].val < queriesWithIndex[j].val\n    })\n    \n    res := make([]int, len(queries))\n    maxBea := 0\n    j := 0\n    for _, q := range queriesWithIndex {\n        for j < len(items) && items[j][0] <= q.val {\n            if items[j][1] > maxBea {\n                maxBea = items[j][1]\n            }\n            j++\n        }\n        res[q.idx] = maxBea\n    }\n    return res\n}\n```\n```swift []\nclass Solution {\n    func maximumBeauty(_ items: [[Int]], _ queries: [Int]) -> [Int] {\n        let sortedItems = items.sorted { $0[0] < $1[0] }\n        let queriesWithIndex = queries.enumerated().map { ($1, $0) }.sorted { $0.0 < $1.0 }\n        \n        var res = Array(repeating: 0, count: queries.count)\n        var maxBea = 0\n        var j = 0\n        \n        for (query, index) in queriesWithIndex {\n            while j < sortedItems.count && sortedItems[j][0] <= query {\n                maxBea = max(maxBea, sortedItems[j][1])\n                j += 1\n            }\n            res[index] = maxBea\n        }\n        return res\n    }\n}\n```\n```javascript [JS]\n// JavaScript\n\nvar maximumBeauty = function(items, queries) {\n    items.sort((a, b) => a[0] - b[0]);\n    const queriesWithIndex = queries.map((q, i) => [q, i])\n                                  .sort((a, b) => a[0] - b[0]);\n    \n    const res = new Array(queries.length).fill(0);\n    let maxBea = 0;\n    let j = 0;\n    \n    for (const [query, index] of queriesWithIndex) {\n        while (j < items.length && items[j][0] <= query) {\n            maxBea = Math.max(maxBea, items[j][1]);\n            j++;\n        }\n        res[index] = maxBea;\n    }\n    return res;\n};\n```\n```typescript [TS]\n// TypeScript\n\nfunction maximumBeauty(items: number[][], queries: number[]): number[] {\n    items.sort((a, b) => a[0] - b[0]);\n    const queriesWithIndex = queries.map((q, i) => [q, i])\n                                  .sort((a, b) => a[0] - b[0]);\n    \n    const res = new Array(queries.length).fill(0);\n    let maxBea = 0;\n    let j = 0;\n    \n    for (const [query, index] of queriesWithIndex) {\n        while (j < items.length && items[j][0] <= query) {\n            maxBea = Math.max(maxBea, items[j][1]);\n            j++;\n        }\n        res[index] = maxBea;\n    }\n    return res;\n}\n```\n```rust []\nimpl Solution {\n    pub fn maximum_beauty(items: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {\n        let mut items = items;\n        items.sort_by_key(|x| x[0]);\n        \n        let mut queries_with_index: Vec<(i32, usize)> = queries.iter()\n            .enumerate()\n            .map(|(i, &q)| (q, i))\n            .collect();\n        queries_with_index.sort_by_key(|&(q, _)| q);\n        \n        let mut res = vec![0; queries.len()];\n        let mut max_bea = 0;\n        let mut j = 0;\n        \n        for (query, index) in queries_with_index {\n            while j < items.len() && items[j][0] <= query {\n                max_bea = max_bea.max(items[j][1]);\n                j += 1;\n            }\n            res[index] = max_bea;\n        }\n        res\n    }\n}\n\n\n```\n```ruby []\ndef maximum_beauty(items, queries)\n    items.sort!\n    queries_with_index = queries.each_with_index.map { |q, i| [q, i] }.sort\n    \n    res = Array.new(queries.size, 0)\n    max_bea = 0\n    j = 0\n    \n    queries_with_index.each do |query, index|\n        while j < items.size && items[j][0] <= query\n            max_bea = [max_bea, items[j][1]].max\n            j += 1\n        end\n        res[index] = max_bea\n    end\n    \n    res\nend\n```\n\n- Complexy: Time O(n log n) and Space O(n)\n\n\n# #2 Sorting + Binary Search (almost all beats 100%)\n\n```python3 []\nclass Solution:\n    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n        sorted_items = sorted(items, key=lambda item: item[0])  # Step 1: Sort items by price\n\n        prices = [item[0] for item in sorted_items] # Step 2: Extract prices and beauties\n        beauties = [item[1] for item in sorted_items]\n        \n        max_beauties = list(accumulate(beauties, max, initial=0)) # Step 3: Create running maximum beauty array\n        \n        result = []     # Step 4: Find maximum beauty for each query price\n        for query_price in queries:\n            index = bisect_right(prices, query_price)\n            result.append(max_beauties[index])  \n        return result\n```\n```cpp []\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        // Step 1: Sort items by price in ascending order\n        sort(items.begin(), items.end());\n        \n        // Step 2: Extract prices and beauties into separate vectors\n        vector<int> prices, beauties;\n        for (const auto& item : items) {\n            prices.push_back(item[0]);\n            beauties.push_back(item[1]);\n        }\n        \n        // Step 3: Create running maximum beauty array\n        vector<int> max_beauties(1, 0);\n        int curr_max = 0;\n        for (int beauty : beauties) {\n            curr_max = max(curr_max, beauty);\n            max_beauties.push_back(curr_max);\n        }\n        \n        // Step 4: Process each query using binary search\n        vector<int> result;\n        for (int query_price : queries) {\n            auto index = upper_bound(prices.begin(), prices.end(), query_price) - prices.begin();\n            result.push_back(max_beauties[index]);\n        }\n        \n        return result;\n    }\n};\n\n```\n```java []\nclass Solution {\n    public int[] maximumBeauty(int[][] items, int[] queries) {\n        // Step 1: Sort items by price in ascending order\n        Arrays.sort(items, (a, b) -> Integer.compare(a[0], b[0]));\n        \n        int n = items.length;\n        // Step 2: Extract prices and beauties into separate arrays\n        int[] prices = new int[n];\n        int[] beauties = new int[n];\n        for (int i = 0; i < n; i++) {\n            prices[i] = items[i][0];\n            beauties[i] = items[i][1];\n        }\n        \n        // Step 3: Create running maximum beauty array\n        int[] maxBeauties = new int[n + 1];\n        for (int i = 0; i < n; i++) {\n            maxBeauties[i + 1] = Math.max(maxBeauties[i], beauties[i]);\n        }\n        \n        // Step 4: Process each query using binary search\n        int[] result = new int[queries.length];\n        for (int i = 0; i < queries.length; i++) {\n            int index = upperBound(prices, queries[i]);\n            result[i] = maxBeauties[index];\n        }\n        \n        return result;\n    }\n    \n    // Helper method for binary search\n    private int upperBound(int[] arr, int target) {\n        int left = 0, right = arr.length;\n        while (left < right) {\n            int mid = left + (right - left) / 2;\n            if (arr[mid] <= target) left = mid + 1;\n            else right = mid;\n        }\n        return left;\n    }\n}\n```\n```csharp []\npublic class Solution {\n    public int[] MaximumBeauty(int[][] items, int[] queries) {\n        // Step 1: Sort items by price in ascending order\n        Array.Sort(items, (a, b) => a[0].CompareTo(b[0]));\n        \n        int n = items.Length;\n        // Step 2: Extract prices and beauties into separate arrays\n        int[] prices = new int[n];\n        int[] beauties = new int[n];\n        for (int i = 0; i < n; i++) {\n            prices[i] = items[i][0];\n            beauties[i] = items[i][1];\n        }\n        \n        // Step 3: Create running maximum beauty array\n        int[] maxBeauties = new int[n + 1];\n        for (int i = 0; i < n; i++) {\n            maxBeauties[i + 1] = Math.Max(maxBeauties[i], beauties[i]);\n        }\n        \n        // Step 4: Process each query using binary search\n        int[] result = new int[queries.Length];\n        for (int i = 0; i < queries.Length; i++) {\n            int index = Array.BinarySearch(prices, queries[i]);\n            if (index < 0) index = ~index;\n            result[i] = maxBeauties[index];\n        }\n        \n        return result;\n    }\n}\n```\n```golang []\nfunc maximumBeauty(items [][]int, queries []int) []int {\n    // Step 1: Sort items by price in ascending order\n    sort.Slice(items, func(i, j int) bool {\n        return items[i][0] < items[j][0]\n    })\n    \n    n := len(items)\n    // Step 2: Extract prices and beauties into separate slices\n    prices := make([]int, n)\n    beauties := make([]int, n)\n    for i, item := range items {\n        prices[i] = item[0]\n        beauties[i] = item[1]\n    }\n    \n    // Step 3: Create running maximum beauty array\n    maxBeauties := make([]int, n+1)\n    for i := 0; i < n; i++ {\n        maxBeauties[i+1] = max(maxBeauties[i], beauties[i])\n    }\n    \n    // Step 4: Process each query using binary search\n    result := make([]int, len(queries))\n    for i, query := range queries {\n        index := sort.SearchInts(prices, query+1)\n        result[i] = maxBeauties[index]\n    }\n    \n    return result\n}\n\nfunc max(a, b int) int {\n    if a > b {\n        return a\n    }\n    return b\n}\n```\n```swift []\nclass Solution {\n    func maximumBeauty(_ items: [[Int]], _ queries: [Int]) -> [Int] {\n        // Step 1: Sort items by price in ascending order\n        let sortedItems = items.sorted { $0[0] < $1[0] }\n        \n        // Step 2: Extract prices and beauties into separate arrays\n        let prices = sortedItems.map { $0[0] }\n        let beauties = sortedItems.map { $0[1] }\n        \n        // Step 3: Create running maximum beauty array\n        var maxBeauties = [0]\n        var currentMax = 0\n        for beauty in beauties {\n            currentMax = max(currentMax, beauty)\n            maxBeauties.append(currentMax)\n        }\n        \n        // Step 4: Process each query using binary search\n        return queries.map { query in\n            let index = prices.firstIndex(where: { $0 > query }) ?? prices.count\n            return maxBeauties[index]\n        }\n    }\n}\n```\n```javascript [JS]\n// JavaScript\n\nvar maximumBeauty = function(items, queries) {\n    // Step 1: Sort items by price\n    items.sort((a, b) => a[0] - b[0]);\n    \n    // Step 2: Extract prices and beauties\n    const prices = items.map(item => item[0]);\n    const beauties = items.map(item => item[1]);\n    \n    // Step 3: Create running maximum beauty array\n    const maxBeauties = [0];\n    let currentMax = 0;\n    for (const beauty of beauties) {\n        currentMax = Math.max(currentMax, beauty);\n        maxBeauties.push(currentMax);\n    }\n    \n    // Step 4: Find maximum beauty for each query price using binary search\n    return queries.map(query => {\n        let left = 0, right = prices.length;\n        while (left < right) {\n            const mid = Math.floor((left + right) / 2);\n            if (prices[mid] <= query) {\n                left = mid + 1;\n            } else {\n                right = mid;\n            }\n        }\n        return maxBeauties[left];\n    });\n};\n```\n```typescript [TS]\n// TypeScript\n\nfunction maximumBeauty(items: number[][], queries: number[]): number[] {\n    // Step 1: Sort items by price in ascending order\n    items.sort((a, b) => a[0] - b[0]);\n    \n    // Step 2: Extract prices and beauties into separate arrays\n    const prices: number[] = items.map(item => item[0]);\n    const beauties: number[] = items.map(item => item[1]);\n    \n    // Step 3: Create running maximum beauty array\n    const maxBeauties: number[] = [0];\n    let currentMax = 0;\n    for (const beauty of beauties) {\n        currentMax = Math.max(currentMax, beauty);\n        maxBeauties.push(currentMax);\n    }\n    \n    // Step 4: Process each query using binary search\n    return queries.map(query => {\n        const index = upperBound(prices, query);\n        return maxBeauties[index];\n    });\n}\n\n// Helper function for binary search\nfunction upperBound(arr: number[], target: number): number {\n    let left = 0, right = arr.length;\n    while (left < right) {\n        const mid = Math.floor((left + right) / 2);\n        if (arr[mid] <= target) left = mid + 1;\n        else right = mid;\n    }\n    return left;\n}\n```\n```rust []\nimpl Solution {\n    pub fn maximum_beauty(mut items: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {\n        // Step 1: Sort items by price in ascending order\n        items.sort_by_key(|item| item[0]);\n        \n        // Step 2: Extract prices and beauties into separate vectors\n        let prices: Vec<i32> = items.iter().map(|item| item[0]).collect();\n        let beauties: Vec<i32> = items.iter().map(|item| item[1]).collect();\n        \n        // Step 3: Create running maximum beauty array\n        let mut max_beauties = vec![0];\n        let mut current_max = 0;\n        for &beauty in beauties.iter() {\n            current_max = current_max.max(beauty);\n            max_beauties.push(current_max);\n        }\n        \n        // Step 4: Process each query using binary search\n        queries.iter().map(|&query| {\n            let index = prices.partition_point(|&x| x <= query);\n            max_beauties[index]\n        }).collect()\n    }\n}\n```\n```ruby []\ndef maximum_beauty(items, queries)\n    # Step 1: Sort items by price\n    items.sort_by! { |item| item[0] }\n    \n    # Step 2: Extract prices and beauties\n    prices = items.map { |item| item[0] }\n    beauties = items.map { |item| item[1] }\n    \n    # Step 3: Create running maximum beauty array\n    max_beauties = [0]\n    current_max = 0\n    beauties.each do |beauty|\n        current_max = [current_max, beauty].max\n        max_beauties << current_max\n    end\n    \n    # Step 4: Find maximum beauty for each query price using binary search\n    queries.map do |query|\n        left = 0\n        right = prices.length\n        while left < right\n            mid = (left + right) / 2\n            if prices[mid] <= query\n                left = mid + 1\n            else\n                right = mid\n            end\n        end\n        max_beauties[left]\n    end\nend\n```\n- Complexy: Time O(n log n) and Space O(n)\n\n\n\n# Step by Step\n\n---\n\n1. Sort all items by price in ascending order making it easier to find items within price ranges\n\n```\nsorted_items = sorted(items, key=lambda item: item[0])\n```\n2. Create two sorted lists\n- `prices`\n- `beauties`\n\n```\nprices = [item[0] for item in sorted_items]\nbeauties = [item[1] for item in sorted_items]\n```\n3. Track Maximum Beauty\n- Create a running maximum beauty array where each position i contains the maximum beauty value seen up to index i.  `initial=0` In case when no items are affordable.\n```\nmax_beauties = list(accumulate(beauties, max, initial=0))\n```\n4. Query Processing\n- Use binary search (bisect_right) to find where the query price woud fit in the sorted prices\n- Looks up the maximum beauty achievable at that price point using the [pre-computed](https://en.wikipedia.org/wiki/Precomputation) `max_beauties` array\n\n```\nfor query_price in queries:\n    index = bisect_right(prices, query_price)\n    result.append(max_beauties[index])\n```\n\n---\n\n# Still dont understand binary search\n- IMO Best explained Binary Search: google "topcoder Binary Search" first \n- Video:\n https://www.youtube.com/watch?v=GU7DpgHINWQ\n\n\n---\n\n\n\n\n![array2.png](https://assets.leetcode.com/users/images/7a0a6937-9d07-4cf6-ad93-d27ffcaf69a0_1730577425.4474297.png)\n\n\n# Most common Array Interview Problems\nList based on my research (interviews, reddit, github) Probably not 100% accurate but very close to my recruitments. Leetcode Premium is probably more accurate [I don\'t have]\n\n\n**Easy:** [[1. Two Sum]](https://leetcode.com/problems/two-sum/solutions/5999466/beats-100-explained-step-by-step-list-most-common-array-inverview) **(common warm-up)** [[121. Best Time to Buy and Sell Stock]](https://leetcode.com/discuss/topic/6027720/solution/) [[88. Merge Sorted Array]](https://leetcode.com/problems/merge-sorted-array/solutions/6031394/beats-100-explained-step-by-step-list-most-common-string-interview-problems) [[27. Remove Element]](https://leetcode.com/problems/remove-element/solutions/6031528/beats-100-explained-step-by-step-list-most-common-array-interview-problems) [[929. Unique Email Addresses]](https://leetcode.com/problems/unique-email-addresses/solutions/6031687/explained-step-by-step-video-list-most-common-array-interview-problems) \n\n\n**Medium/Hard:** [[15. 3Sum]](https://leetcode.com/problems/3sum/description/) [[42. Trapping Rain Water]](https://leetcode.com/problems/trapping-rain-water/?envType=problem-list-v2&envId=atbyk0mj) [[56. Merge Intervals]](https://leetcode.com/problems/merge-intervals/description/) [[57. Insert Interval]](https://leetcode.com/problems/insert-interval/description/) [[46. Permutations]](https://leetcode.com/problems/permutations/description/) [[53. Maximum Subarray]](https://leetcode.com/problems/maximum-subarray/description/) [[73. Set Matrix Zeroes]](https://leetcode.com/problems/set-matrix-zeroes/description/) [[284. Peeking Iterator]](https://leetcode.com/problems/peeking-iterator/description/)\n\n\n####  [Interview Questions and Answers Repository](https://github.com/RooTinfinite/Interview-questions-and-answers)\n\n\n\n\n![image.png](https://assets.leetcode.com/users/images/9dc1b265-b175-4bf4-bc6c-4b188cb79220_1728176037.4402142.png)\n![image.png](https://assets.leetcode.com/users/images/5d0fc970-c2ab-4b0b-a7bf-a0e6ba187fd6_1731370907.1147695.png)\n![image.png](https://assets.leetcode.com/users/images/0f30dc02-0bbd-4c64-b979-a30574dbc938_1731374785.691469.png)\n
['Swift', 'C++', 'Java', 'Go', 'TypeScript', 'Python3', 'Rust', 'Ruby', 'JavaScript', 'C#']