easy Range Minimum Query

Problem Statement

You are given an array nums containing n integers and a 2D array queries of length q, where queries[i] = [start_i, end_i], 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_i < end_i <= 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 time. Once the tree is built, we can answer any range minimum query in 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].

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

import java.util.Arrays;

class Solution {

  // Recursive function to get the minimum value in a given range of array indexes
  int rangeMinQuery(
    int[] segmentTree,
    int segmentStart,
    int segmentEnd,
    int queryStart,
    int queryEnd,
    int index
  ) {
    // If the segment of this node is a part of the given range
    if (
      queryStart <= segmentStart && queryEnd >= segmentEnd
    ) return segmentTree[index];

    // If the segment of this node is outside the given range
    if (
      segmentEnd < queryStart || segmentStart > queryEnd
    ) return Integer.MAX_VALUE;

    // If a part of this segment overlaps with the given range
    int mid = segmentStart + (segmentEnd - segmentStart) / 2;
    return Math.min(
      rangeMinQuery(
        segmentTree,
        segmentStart,
        mid,
        queryStart,
        queryEnd,
        2 * index + 1
      ),
      rangeMinQuery(
        segmentTree,
        mid + 1,
        segmentEnd,
        queryStart,
        queryEnd,
        2 * index + 2
      )
    );
  }

  // Return minimum of elements in range from index queryStart to queryEnd
  int[] rangeMinQueryAll(int[] segmentTree, int n, int[][] queries) {
    int[] results = new int[queries.length];

    for (int i = 0; i < queries.length; i++) {
      int queryStart = queries[i][0];
      int queryEnd = queries[i][1];

      results[i] = rangeMinQuery(
        segmentTree,
        0,
        n - 1,
        queryStart,
        queryEnd,
        0
      );
    }

    return results;
  }

  // Recursive function that constructs Segment Tree for array[segmentStart..segmentEnd]
  int constructSegmentTree(
    int[] nums,
    int segmentStart,
    int segmentEnd,
    int[] segmentTree,
    int index
  ) {
    // If there is one element in the array, store it in the current node of the segment tree and return
    if (segmentStart == segmentEnd) {
      segmentTree[index] = nums[segmentStart];
      return nums[segmentStart];
    }

    // If there are more than one elements, then recur for left and right subtrees
    int mid = segmentStart + (segmentEnd - segmentStart) / 2;
    segmentTree[index] = Math.min(
      constructSegmentTree(nums, segmentStart, mid, segmentTree, index * 2 + 1),
      constructSegmentTree(
        nums,
        mid + 1,
        segmentEnd,
        segmentTree,
        index * 2 + 2
      )
    );
    return segmentTree[index];
  }

  // Function to construct segment tree from given array
  int[] constructSegmentTree(int[] nums, int n) {
    // Height of segment tree
    int height = (int) (Math.ceil(Math.log(n) / Math.log(2)));

    // Maximum size of segment tree
    int maxSize = 2 * (int) Math.pow(2, height) - 1;
    int[] segmentTree = new int[maxSize];

    // Fill the allocated memory segmentTree
    constructSegmentTree(nums, 0, n - 1, segmentTree, 0);

    // Return the constructed segment tree
    return segmentTree;
  }

  // Wrapper method to construct segment tree and process queries
  int[] processQueries(int[] nums, int[][] queries) {
    int[] segmentTree = constructSegmentTree(nums, nums.length);
    return rangeMinQueryAll(segmentTree, nums.length, queries);
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    int[] nums1 = { 2, 6, 1, 12, 9, 5, 3, 7 };
    int[][] queries1 = {
      { 0, 3 },
      { 2, 5 },
      { 0, 1 },
      { 3, 7 },
      { 0, 7 },
      { 4, 6 },
      { 4, 5 },
    };
    int[] results1 = sol.processQueries(nums1, queries1);

    System.out.println("Example 1: ");
    for (int i = 0; i < queries1.length; i++) {
      System.out.println(
        "Range [" +
          queries1[i][0] +
          ", " +
          queries1[i][1] +
          "] -> Minimum: " +
          results1[i]
      );
    }

    int[] nums2 = { 4, 8, 6, 2, 10, 15 };
    int[][] queries2 = { { 1, 3 }, { 0, 2 }, { 2, 4 }, { 3, 5 } };
    int[] results2 = sol.processQueries(nums2, queries2);

    System.out.println("Example 2: ");
    for (int i = 0; i < queries2.length; i++) {
      System.out.println(
        "Range [" +
          queries2[i][0] +
          ", " +
          queries2[i][1] +
          "] -> Minimum: " +
          results2[i]
      );
    }

    int[] nums3 = { 11, 13, 5, 8, 10, 12, 7, 14 };
    int[][] queries3 = { { 0, 4 }, { 1, 3 }, { 2, 5 }, { 3, 6 } };
    int[] results3 = sol.processQueries(nums3, queries3);

    System.out.println("Example 3: ");
    for (int i = 0; i < queries3.length; i++) {
      System.out.println(
        "Range [" +
          queries3[i][0] +
          ", " +
          queries3[i][1] +
          "] -> Minimum: " +
          results3[i]
      );
    }
  }
}

Complexity Analysis

Time Complexity

• Segment Tree Construction:

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

• Range Minimum Query:

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

• Overall Time Complexity:

  • 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:
   • 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^{log n} - 1, which simplifies to .