Efficient SortedSet Queries

Efficient SortedSet Queries | CodeSignal Learn

Introduction

Greetings, aspiring coders! Today, we're going to delve deep into the complexities of data structures, specifically the SortedSet in Scala, and explore how to handle queries efficiently. This is a common problem, often encountered in numerous data science and algorithmic problems. So, let's gear up to unravel the mysteries of sorted set operations and get our hands dirty with some interactive problem-solving!

SortedSet Operations and Time Complexity

O(\log N)

Finding Insertion Points and Lower Bounds in Scala

O(\log N)

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Before delving into the task, let's understand what a SortedSet (or TreeSet) is and why we would use it in Scala. A SortedSet is a collection that maintains its elements in sorted order at all times. In Scala, the most common implementation is TreeSet, which is backed by a balanced binary search tree.

Advantages of using SortedSet or TreeSet:

Extracting the minimum (set.headOption) or maximum (set.lastOption) values is a constant or logarithmic time operation, as the set is always kept in sorted order.
Inserting or removing elements is efficient, with a time complexity of $O(\log N)$ per operation, since the underlying tree structure maintains order automatically.
Searching for the existence of an element, or finding the smallest element greater than or equal to a given value, can also be performed efficiently.

Understanding these operations can help us utilize SortedSet efficiently for our problem.

Unlike some languages, Scala's SortedSet does not provide direct methods like bisect_left or bisect_right to find insertion points. However, we can still efficiently find the smallest element greater than or equal to a given value using the from method, which returns a view of the set starting from a specific value.

For example, if we have a TreeSet as TreeSet(1, 2, 4, 6, 8), we can find the smallest element greater than or equal to 4 by calling set.from(4).headOption. This will return Some(4), since 4 is present in the set. If we call set.from(5).headOption, it will return Some(6), as 6 is the next greater element.

Both insertion and search operations in a TreeSet are performed in $O(\log N)$ time.

Here is an example of how you would use from and headOption on a TreeSet:

Scala

import scala.collection.immutable.TreeSet

val set = TreeSet(1, 2, 4, 4, 6)
val idx1 = set.from(4).headOption // Some(4)
val idx2 = set.from(5).headOption // Some(6)
println(idx1, idx2) // Output: (Some(4), Some(6))

Task Statement

We are tasked with designing a Scala function named processQueries that can process a series of distinct requests or queries efficiently. The queries comprise a list of two integers — the type of operation and the operand. There are three types of operations we'll handle: Adding an integer to the set (operation type 0) Removing an integer from the set (operation type 1). Whenever this operation is invoked, we can guarantee that the integer exists in the set. Finding the smallest integer that is greater than or equal to a given value (operation type 2). The function should return the current size of the set when the operation type is 0 or 1, and the smallest possible integer when the operation type is 2. If such an integer does not exist, the function should return -1. Given a list of queries: Scala List(List(0, 10), List(2, 10), List(0, 20), List(1, 10), List(2, 10)) List(List(0, 10), List(2, 10), List(0, 20), List(1, 10), List(2, 10)) The function should return: List(1, 10, 2, 1, 20)

Solution Building: Step 1

To start, we'll initialize our TreeSet in Scala. We'll also create an empty ListBuffer labeled results to store the outputs for each request. Scala import scala.collection.immutable.TreeSet import scala.collection.mutable.ListBuffer def processQueries(queries: List[List[Int]]): List[Int] = {var set = TreeSet.empty[Int] val results = ListBuffer.empty[Int] // Further logic will go here} import scala.collection.immutable.TreeSet import scala.collection.mutable.ListBuffer def processQueries(queries: List[List[Int]]): List[Int] = {var set = TreeSet.empty[Int] val results = ListBuffer.empty[Int] // Further logic will go here}

Solution Building: Step 2

Next, we utilize a for loop to traverse through all the queries. For an operation type of 0 or 1, we either add or remove the provided value from our sorted set. Subsequently, we append the size of the current set to results . Scala import scala.collection.immutable.TreeSet import scala.collection.mutable.ListBuffer def processQueries(queries: List[List[Int]]): List[Int] = {var set = TreeSet.empty[Int] val results = ListBuffer.empty[Int] for (query <- queries) {val operation = query(0) val value = query(1) operation match {case 0 => set += value results += set.size case 1 => set -= value results += set.size // We'll handle operation 2 in the next step case 2 => // Placeholder for now}} results.toList} import scala.collection.immutable.TreeSet import scala.collection.mutable.ListBuffer def processQueries(queries: List[List[Int]]): List[Int] = {var set = TreeSet.empty[Int] val results = ListBuffer.empty[Int] for (query <- queries) {val operation = query(0) val value = query(1) operation match {case 0 => set += value results += set.size case 1 => set -= value results += set.size // We'll handle operation 2 in the next step case 2 => // Placeholder for now}} results.toList}

Solution Building: Step 3

Lastly, when the operation type is 2, we need to find the minimum bound, i.e., the smallest value greater than or equal to our provided value in the set. We perform this using the from method and headOption from our TreeSet . If such a value does not exist, we append -1 to results . Scala import scala.collection.immutable.TreeSet import scala.collection.mutable.ListBuffer def processQueries(queries: List[List[Int]]): List[Int] = {var set = TreeSet.empty[Int] val results = ListBuffer.empty[Int] for (query <- queries) {val operation = query(0) val value = query(1) operation match {case 0 => set += value results += set.size case 1 => set -= value results += set.size case 2 => val maybeValue = set.from(value).headOption results += maybeValue.getOrElse(-1)}} results.toList} import scala.collection.immutable.TreeSet import scala.collection.mutable.ListBuffer def processQueries(queries: List[List[Int]]): List[Int] = {var set = TreeSet.empty[Int] val results = ListBuffer.empty[Int] for (query <- queries) {val operation = query(0) val value = query(1) operation match {case 0 => set += value results += set.size case 1 => set -= value results += set.size case 2 => val maybeValue = set.from(value).headOption results += maybeValue.getOrElse(-1)}} results.toList}