1651. Hopper Company Queries III - Leetcode Solution

Problem Description

The "Hopper Company Queries III" problem describes a scenario where you are given a set of n companies, each with a certain value. You are required to efficiently process q queries of two types:

Update Query: Update the value of a company at a specific index.
Range Query: Find the maximum value among companies within a given range of indices.

The challenge is to handle both types of queries quickly, especially since the number of queries and companies can be large (up to 10⁵). You must design a data structure that supports fast updates and fast range maximum queries.

Key constraints:

Each operation must be efficient (ideally O(log n) or better).
There may be up to 10⁵ companies and queries.
Updates and queries can be interleaved in any order.

The goal is to implement a class or function that can process these queries efficiently.

Thought Process

The first idea that comes to mind is to use a simple array to represent the companies and, for each query, scan the relevant range to find the maximum. However, this brute-force approach would take O(n) time for each range query, which is too slow for large inputs.

To optimize, we want a data structure that supports both point updates and range maximum queries in logarithmic time. Segment Trees and Binary Indexed Trees (Fenwick Trees) are classic solutions for this type of problem. Since we need to support range maximum (not sum), a Segment Tree is better suited.

By building a Segment Tree, we can:

Update the value of a single company in O(log n) time.
Query the maximum value in a range in O(log n) time.

This approach is much faster and scalable for the given constraints.

Solution Approach

We'll use a Segment Tree to efficiently handle both update and range maximum queries. Here's how we approach the problem step-by-step:

Initialization:
- Build a Segment Tree from the initial array of company values.
- Each node in the tree stores the maximum value in a segment (range) of the array.
Update Query:
- When updating the value at index i, update the corresponding leaf node in the Segment Tree.
- Propagate the change upwards, updating all affected parent nodes to maintain correct maximums.
Range Query:
- Given a range [l, r], use the Segment Tree to efficiently compute the maximum value in that range.
- Traverse the tree, combining results from relevant segments, in O(log n) time.
Design Choices:
- We use a Segment Tree over a Binary Indexed Tree because we need range maximum queries, not just sums.
- Segment Tree is flexible and supports both update and query efficiently.

This approach ensures both types of queries are handled quickly, even for large datasets.

Example Walkthrough

Let's walk through an example:
Input:

Initial company values: [5, 3, 8, 6, 2]
Queries:

Query 1: Update index 2 to 10 (company values become [5, 3, 10, 6, 2])
Query 2: Find max in range [1, 3] (indices 1 to 3: 3, 10, 6)
Query 3: Update index 4 to 7 (company values become [5, 3, 10, 6, 7])
Query 4: Find max in range [0, 4] (entire array: 5, 3, 10, 6, 7)

Step-by-step:

Update index 2 to 10: Segment Tree is updated, propagating the new value up the tree.
Range max [1, 3]: The Segment Tree returns 10 as the maximum in this range.
Update index 4 to 7: Segment Tree is updated accordingly.
Range max [0, 4]: The Segment Tree returns 10 as the maximum in the entire array.

At each step, both updates and queries are handled efficiently, with no need to scan the array directly.

Time and Space Complexity

Brute-Force Approach:

Update: O(1) (just change one element)
Range Query: O(n) (scan the range each time)
Total for q queries: O(qn) in the worst case, which is too slow for large n and q.

Optimized (Segment Tree) Approach:

Build Segment Tree: O(n)
Update: O(log n) per update
Range Query: O(log n) per query
Total for q queries: O((n + q) log n), which is efficient for large datasets.
Space Complexity: O(n) for the Segment Tree.

The Segment Tree's logarithmic time for updates and queries is the key to handling large numbers of operations efficiently.

Summary

In summary, the "Hopper Company Queries III" problem is a classic example of efficiently handling dynamic range queries and updates. By using a Segment Tree, we achieve fast O(log n) time for both update and range maximum queries, making the solution scalable for large inputs. The key insight is choosing the right data structure for the job, and understanding how to implement and use it effectively. This approach is elegant because it balances both types of operations, ensuring the system remains efficient no matter how the queries are interleaved.

Code Implementation

class SegmentTree:
    def __init__(self, arr):
        n = len(arr)
        self.n = n
        self.tree = [0] * (4 * n)
        self.build(arr, 0, 0, n-1)

    def build(self, arr, node, l, r):
        if l == r:
            self.tree[node] = arr[l]
        else:
            mid = (l + r) // 2
            self.build(arr, 2*node+1, l, mid)
            self.build(arr, 2*node+2, mid+1, r)
            self.tree[node] = max(self.tree[2*node+1], self.tree[2*node+2])

    def update(self, idx, value, node=0, l=0, r=None):
        if r is None:
            r = self.n - 1
        if l == r:
            self.tree[node] = value
        else:
            mid = (l + r) // 2
            if idx <= mid:
                self.update(idx, value, 2*node+1, l, mid)
            else:
                self.update(idx, value, 2*node+2, mid+1, r)
            self.tree[node] = max(self.tree[2*node+1], self.tree[2*node+2])

    def query(self, ql, qr, node=0, l=0, r=None):
        if r is None:
            r = self.n - 1
        if qr < l or ql > r:
            return float('-inf')
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        left = self.query(ql, qr, 2*node+1, l, mid)
        right = self.query(ql, qr, 2*node+2, mid+1, r)
        return max(left, right)

# Example usage:
# arr = [5, 3, 8, 6, 2]
# st = SegmentTree(arr)
# st.update(2, 10)  # Update index 2 to 10
# print(st.query(1, 3))  # Query max from index 1 to 3
# st.update(4, 7)
# print(st.query(0, 4))

#include <vector>
#include <algorithm>
using namespace std;

class SegmentTree {
    vector<int> tree;
    int n;

    void build(vector<int>& arr, int node, int l, int r) {
        if (l == r) {
            tree[node] = arr[l];
        } else {
            int mid = (l + r) / 2;
            build(arr, 2*node+1, l, mid);
            build(arr, 2*node+2, mid+1, r);
            tree[node] = max(tree[2*node+1], tree[2*node+2]);
        }
    }

    void update(int idx, int value, int node, int l, int r) {
        if (l == r) {
            tree[node] = value;
        } else {
            int mid = (l + r) / 2;
            if (idx <= mid)
                update(idx, value, 2*node+1, l, mid);
            else
                update(idx, value, 2*node+2, mid+1, r);
            tree[node] = max(tree[2*node+1], tree[2*node+2]);
        }
    }

    int query(int ql, int qr, int node, int l, int r) {
        if (qr < l || ql > r)
            return INT_MIN;
        if (ql <= l && r <= qr)
            return tree[node];
        int mid = (l + r) / 2;
        int left = query(ql, qr, 2*node+1, l, mid);
        int right = query(ql, qr, 2*node+2, mid+1, r);
        return max(left, right);
    }

public:
    SegmentTree(vector<int>& arr) {
        n = arr.size();
        tree.resize(4*n);
        build(arr, 0, 0, n-1);
    }

    void update(int idx, int value) {
        update(idx, value, 0, 0, n-1);
    }

    int query(int l, int r) {
        return query(l, r, 0, 0, n-1);
    }
};

// Example usage:
// vector<int> arr = {5, 3, 8, 6, 2};
// SegmentTree st(arr);
// st.update(2, 10);
// int res1 = st.query(1, 3);
// st.update(4, 7);
// int res2 = st.query(0, 4);

class SegmentTree {
    int[] tree;
    int n;

    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[4 * n];
        build(arr, 0, 0, n - 1);
    }

    private void build(int[] arr, int node, int l, int r) {
        if (l == r) {
            tree[node] = arr[l];
        } else {
            int mid = (l + r) / 2;
            build(arr, 2 * node + 1, l, mid);
            build(arr, 2 * node + 2, mid + 1, r);
            tree[node] = Math.max(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    public void update(int idx, int value) {
        update(idx, value, 0, 0, n - 1);
    }

    private void update(int idx, int value, int node, int l, int r) {
        if (l == r) {
            tree[node] = value;
        } else {
            int mid = (l + r) / 2;
            if (idx <= mid)
                update(idx, value, 2 * node + 1, l, mid);
            else
                update(idx, value, 2 * node + 2, mid + 1, r);
            tree[node] = Math.max(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    public int query(int l, int r) {
        return query(l, r, 0, 0, n - 1);
    }

    private int query(int ql, int qr, int node, int l, int r) {
        if (qr < l || ql > r)
            return Integer.MIN_VALUE;
        if (ql <= l && r <= qr)
            return tree[node];
        int mid = (l + r) / 2;
        int left = query(ql, qr, 2 * node + 1, l, mid);
        int right = query(ql, qr, 2 * node + 2, mid + 1, r);
        return Math.max(left, right);
    }
}

// Example usage:
// int[] arr = {5, 3, 8, 6, 2};
// SegmentTree st = new SegmentTree(arr);
// st.update(2, 10);
// int res1 = st.query(1, 3);
// st.update(4, 7);
// int res2 = st.query(0, 4);

class SegmentTree {
    constructor(arr) {
        this.n = arr.length;
        this.tree = new Array(4 * this.n).fill(0);
        this.build(arr, 0, 0, this.n - 1);
    }

    build(arr, node, l, r) {
        if (l === r) {
            this.tree[node] = arr[l];
        } else {
            const mid = Math.floor((l + r) / 2);
            this.build(arr, 2 * node + 1, l, mid);
            this.build(arr, 2 * node + 2, mid + 1, r);
            this.tree[node] = Math.max(this.tree[2 * node + 1], this.tree[2 * node + 2]);
        }
    }

    update(idx, value, node = 0, l = 0, r = this.n - 1) {
        if (l === r) {
            this.tree[node] = value;
        } else {
            const mid = Math.floor((l + r) / 2);
            if (idx <= mid) {
                this.update(idx, value, 2 * node + 1, l, mid);
            } else {
                this.update(idx, value, 2 * node + 2, mid + 1, r);
            }
            this.tree[node] = Math.max(this.tree[2 * node + 1], this.tree[2 * node + 2]);
        }
    }

    query(ql, qr, node = 0, l = 0, r = this.n - 1) {
        if (qr < l || ql > r) {
            return -Infinity;
        }
        if (ql <= l && r <= qr) {
            return this.tree[node];
        }
        const mid = Math.floor((l + r) / 2);
        const left = this.query(ql, qr, 2 * node + 1, l, mid);
        const right = this.query(ql, qr, 2 * node + 2, mid + 1, r);
        return Math.max(left, right);
    }
}

// Example usage:
// let arr = [5, 3, 8, 6, 2];
// let st = new SegmentTree(arr);
// st.update(2, 10);
// console.log(st.query(1, 3));
// st.update(4, 7);
// console.log(st.query(0, 4));

AlgoMap.io

Want Help Cracking FAANG?