Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Problem statement
3.
Approach
4.
Code
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

# Queries to Find The First Array Element Exceeding K with Updates

Malay Gain
0 upvote

## Introduction

Finding the first array element exceeding K is not a very difficult task. By just array traversal we can find the required answer. But here we will implement an efficient approach to solve this problem. If we take the brute force approach, it will take O(q*n) time for q such queries. Here we will solve the problem efficiently using a segment tree.

## Problem statement

There is an array of integers. You are given some queries of format {1,k} to find the first array element exceeding k (i.e. greater or equal to the value k) and some queries of format {2,i,val} to update the array element at ith index with val.

Input

arr[ ] = {2, 4, 7, 8, 6}

Q= { { 1, 5 },  { 2, 3, 5 }, { 1, 4 },  { 1, 8 } }

Output

2

1

-1

Explanation

arr[ ]= {2, 4, 7, 8, 6}

0   1  2  3  4(indices)

So, for the {1,5} query we need to find the index of the first element exceeding 5 i.e.  2 as arr[2]=7.

Updated array after the query { 2, 3, 5 };  arr[ ]= {2, 4, 7, 5, 6}

Similarly, the output of the {1,4} query is 1.

As the updated array doesn’t contain any value exceeding 8, the output of the {1,8} query is -1.

Note: Please try to solve the problem first and then see the below solution approach.

Also see, Euclid GCD Algorithm

## Approach

Here we will construct a segment tree st following the same way as range minimum query problem. The only difference for this case is instead of minimum, each node will store the maximum of its subtrees.

To find first array element exceeding k, we will define a function findMinIndex(idx,low,high,k,st)

• Recursively check if the root of the left subtree is greater than or equal to k. If condition satisfied find the minimum index of the array element from the left subtree.
• Otherwise check in the right subtree and recursively find the position.

For update operation, define a function update(idx,val,low,high,si) to update value at index idx with val.

• If idx is less than or equal to the mid of the range [low,high], traverse to left subtree update(idx,val,low,mid,2*si+1). Otherwise, raverse to right subtree by calling update(idx,val,mid+1,high,2*si+2)

• When low=high, we are at a leaf node of the segment tree which denotes idx of the given array. Update the value of the node st[low] as well as arr[idx].

## Code

Output

Complexity

Time complexity of the above approach O(n*log n + q*log n) where (nlogn) is time for constructing segment tree and (q*log n) is the time required for q queries.

Space complexity is O(n) as extra space is used for constructing a segment tree.

Check out this problem - First And Last Occurrences Of X

## FAQs

1. What is a segment tree?
A segment tree is a special kind of data structure that is used to store information about intervals or segments of an array. It can be represented by an array.

2. What kind of problem can be solved efficiently using segment tree?
A segment tree is used to solve min, max, or sum queries for a given range on an array as well as update queries in O(log n) time where n is the size of the array.

## Key Takeaways

This article covered how to find the first array element exceeding K with updates using segment tree.

To know about more about segment tree you can go through the articles of Coding Ninjas Studio library.

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here.

Happy learning!

Live masterclass