Grokking Advanced Coding Patterns for Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Range Minimum Query
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

You are given an array nums containing n integers and a 2D array queries of length q, where queries[i] = [start<sub>i</sub>, end<sub>i</sub>], representing a starting and ending range (inclusive).

Return an array of size q, where each element is the minimum value in the respective range from nums.

Examples

Example 1:

  • Input: nums = [2, 6, 1, 12, 9, 5, 3, 7], queries = [[0, 3], [2, 5], [0, 1], [3, 7], [0, 7], [4, 6], [4, 5]]
  • Output: [1, 1, 2, 3, 1, 3, 5]
  • Justification:
    • For the range [0, 3], the minimum is 1.
    • For the range [2, 5], the minimum is 1.
    • For the range [0, 1], the minimum is 2.
    • For the range [3, 7], the minimum is 3.
    • For the range [0, 7], the minimum is 1.
    • For the range [4, 6], the minimum is 3.
    • For the range [4, 5], the minimum is 5.

Example 2:

  • Input: nums = [4, 8, 6, 2, 10, 15], queries = [[1, 3], [0, 2], [2, 4], [3, 5]]
  • Output: [2, 4, 2, 2]
  • Justification:
    • For the range [1, 3], the minimum is 2.
    • For the range [0, 2], the minimum is 4.
    • For the range [2, 4], the minimum is 2.
    • For the range [3, 5], the minimum is 2.

Example 3:

  • Input: nums = [11, 13, 5, 8, 10, 12, 7, 14], queries = [[0, 4], [1, 3], [2, 5], [3, 6]]
  • Output: [5, 5, 5, 7]
  • Justification:
    • For the range [0, 4], the minimum is 5.
    • For the range [1, 3], the minimum is 5.
    • For the range [2, 5], the minimum is 5.
    • For the range [3, 6], the minimum is 7.

Constraints:

  • 0 <= start<sub>i</sub> < end<sub>i</sub> <= 1000

Solution

To solve this problem, we will use a Segment Tree. A Segment Tree is a data structure that allows answering range queries in logarithmic time. The idea is to build a binary tree where each node represents a segment (or interval) of the array. The leaf nodes represent single elements, and the internal nodes store the minimum value of their respective children. This way, querying for the minimum value in any range can be done efficiently.

We will first construct the Segment Tree from the given array. This construction takes O(n) time. Once the tree is built, we can answer any range minimum query in O(log n) time. For each query, we will traverse the tree to find the minimum value in the specified range.

Step-by-Step Algorithm

Construct Segment Tree

  1. Compute Height and Maximum Size:

    • Step 1: Calculate the height of the segment tree using ceil(log2(n)). This gives the number of levels needed to cover all elements of the array.
    • Step 2: Calculate the maximum size of the segment tree array using 2 * (2^height) - 1. This size ensures enough space for all nodes in the tree.
    • Step 3: Initialize the segment tree array with the calculated maximum size, typically filled with a 0 initially.

  2. Build the Segment Tree:

    • Step 1: Start the construction with the root node, which represents the entire range of the array nums, i.e., from segmentStart = 0 to segmentEnd = n-1.
    • Step 2: If the current segment represents a single element (i.e., segmentStart == segmentEnd), store the value of that element in the current node of the segment tree.
    • Step 3: Recursively build the left and right subtrees.
      • Step 3.1: Compute the middle index of the current segment using mid = segmentStart + (segmentEnd - segmentStart) / 2.
      • Step 3.2: Recursively build the left subtree with the range [segmentStart, mid].
      • Step 3.3: Recursively build the right subtree with the range [mid + 1, segmentEnd].
    • Step 4: For internal nodes, store the minimum value of their left and right children. This is done by assigning segmentTree[index] = Math.min(segmentTree[leftChildIndex], segmentTree[rightChildIndex]).

Query the Segment Tree

  1. Process Each Query:
    • Step 1: For each query [queryStart, queryEnd], start from the root node representing the range [0, n-1].
    • Step 2: Recursively check the overlap between the query range and the current segment:
      • Step 2.1: If the query range fully covers the current segment, return the value stored in the current node.
      • Step 2.2: If the query range lies completely outside the current segment, return a large value (e.g., Integer.MAX_VALUE).
      • Step 2.3: If the query range partially overlaps with the current segment, recursively query the left and right children.
        • Step 2.3.1: Compute the middle index of the current segment.
        • Step 2.3.2: Recursively query the left subtree for the range [segmentStart, mid].
        • Step 2.3.3: Recursively query the right subtree for the range [mid + 1, segmentEnd].
    • Step 3: Return the minimum of the values obtained from the left and right subtrees for the partially overlapping segments.

Algorithm Walkthrough

Let's consider the input [2, 6, 1, 12, 9, 5, 3, 7].

Image

Construct Segment Tree

  1. Initialization:

    • Height Calculation: Given n = 8, the height of the segment tree is ceil(log2(8)) = 3.
    • Maximum Size Calculation: The maximum size of the segment tree is 2 * (2^3) - 1 = 15.
    • Segment Tree Initialization: Initialize segmentTree = new int[15] with all values set to Integer.MAX_VALUE.

  2. Building the Tree:

    • Root Node (index 0, range [0, 7]):
      • Compute Middle Index: mid = 0 + (7 - 0) / 2 = 3
      • Build Left Subtree (index 1, range [0, 3]):
        • Compute Middle Index: mid = 0 + (3 - 0) / 2 = 1
        • Build Left Subtree (index 3, range [0, 1]):
          • Compute Middle Index: mid = 0 + (1 - 0) / 2 = 0
          • Build Left Leaf Node (index 7, range [0, 0]):
            • Store segmentTree[7] = nums[0] = 2
          • Build Right Leaf Node (index 8, range [1, 1]):
            • Store segmentTree[8] = nums[1] = 6
          • Internal Node (index 3):
            • Store segmentTree[3] = Math.min(segmentTree[7], segmentTree[8]) = Math.min(2, 6) = 2
        • Build Right Subtree (index 4, range [2, 3]):
          • Compute Middle Index: mid = 2 + (3 - 2) / 2 = 2
          • Build Left Leaf Node (index 9, range [2, 2]):
            • Store segmentTree[9] = nums[2] = 1
          • Build Right Leaf Node (index 10, range [3, 3]):
            • Store segmentTree[10] = nums[3] = 12
          • Internal Node (index 4):
            • Store segmentTree[4] = Math.min(segmentTree[9], segmentTree[10]) = Math.min(1, 12) = 1
        • Internal Node (index 1):
          • Store segmentTree[1] = Math.min(segmentTree[3], segmentTree[4]) = Math.min(2, 1) = 1
      • Build Right Subtree (index 2, range [4, 7]):
        • Compute Middle Index: mid = 4 + (7 - 4) / 2 = 5
        • Build Left Subtree (index 5, range [4, 5]):
          • Compute Middle Index: mid = 4 + (5 - 4) / 2 = 4
          • Build Left Leaf Node (index 11, range [4, 4]):
            • Store segmentTree[11] = nums[4] = 9
          • Build Right Leaf Node (index 12, range [5, 5]):
            • Store segmentTree[12] = nums[5] = 5
          • Internal Node (index 5):
            • Store segmentTree[5] = Math.min(segmentTree[11], segmentTree[12]) = Math.min(9, 5) = 5
        • Build Right Subtree (index 6, range [6, 7]):
          • Compute Middle Index: mid = 6 + (7 - 6) / 2 = 6
          • Build Left Leaf Node (index 13, range [6, 6]):
            • Store segmentTree[13] = nums[6] = 3
          • Build Right Leaf Node (index 14, range [7, 7]):
            • Store segmentTree[14] = nums[7] = 7
          • Internal Node (index 6):
            • Store segmentTree[6] = Math.min(segmentTree[13], segmentTree[14]) = Math.min(3, 7) = 3
        • Internal Node (index 2):
          • Store segmentTree[2] = Math.min(segmentTree[5], segmentTree[6]) = Math.min(5, 3) = 3
      • Root Node (index 0):
        • Store segmentTree[0] = Math.min(segmentTree[1], segmentTree[2]) = Math.min(1, 3) = 1 The segment tree is `[1, 1, 3, 2, 1, 5, 3, 2, 6, 1, 12, 9, 5, 3, 7]

Query the Segment Tree

  1. Query [0, 3]:

    • Root Node (range [0, 7]):
      • Query range [0, 3] partially overlaps, check left (range [0, 3]) and right (range [4, 7]) subtrees.
      • Left Subtree (range [0, 3]):
        • Query range fully overlaps, return segmentTree[1] = 1
    • Result: 1

  2. Query [2, 5]:

    • Root Node (range [0, 7]):
      • Query range [2, 5] partially overlaps, check left (range [0, 3]) and right (range [4, 7]) subtrees.
      • Left Subtree (range [0, 3]):
        • Query range [2, 3] partially overlaps, check left (range [0, 1]) and right (range [2, 3]) subtrees.
        • Right Subtree (range [2, 3]):
          • Query range fully overlaps, return segmentTree[4] = 1
      • Right Subtree (range [4, 7]):
        • Query range [4, 5] partially overlaps, check left (range [4, 5]) subtree.
        • Left Subtree (range [4, 5]):
          • Query range fully overlaps, return segmentTree[5] = 5
      • Return minimum of the results: min(1,5) = 1
    • Result: 1

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Segment Tree Construction: O(n)

    • Building the segment tree takes linear time because each node in the segment tree is visited once during construction.

  • Range Minimum Query: O(q*log n)

    • Each query operation takes logarithmic time due to the height of the segment tree being log n. The query function traverses the tree's height, which is log n, visiting up to two branches at each level. For q queries, the total time complexity is the O(q*log n).

  • Overall Time Complexity: O(n) + O(q log n)

    • The overall time complexity is the sum of the time required to construct the segment tree and the time required to answer q range minimum queries.

Space Complexity

  1. Segment Tree Storage: O(n)
    • The space required to store the segment tree is linear with respect to the number of elements in the input array nums. The segment tree array's size is approximately 2 * 2<sup>log n</sup> - 1, which simplifies to O(n).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible