Efficient Queries Using Java TreeSet

Introduction to Efficient Queries Using Java TreeSet

Greetings, aspiring coders! Today, we're going to delve deep into the complexities of data structures, specifically the TreeSet from Java's Collection Framework, 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 TreeSet operations and get our hands dirty with some interactive problem-solving!

TreeSet Operations and Time Complexity

O(1)

Task Statement

We are tasked with designing a Java 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: Java List<int[]> queries = Arrays.asList(new int[]{0, 10}, new int[]{2, 10}, new int[]{0, 20}, new int[]{1, 10}, new int[]{2, 10}); The function should return: [1, 10, 2, 1, 20]

Solution Building: Step 1

Join the 1M+ learners on CodeSignal

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

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 TreeSet.ceiling operation. If such a value does not exist, we append -1 to results.

Java

import java.util.*;

public class EfficientQueries {
    public static List<Integer> processQueries(List<int[]> queries) {
        TreeSet<Integer> sortedSet = new TreeSet<>();
        List<Integer> results = new ArrayList<>();

        for (int[] query : queries) {
            int operation = query[0];
            int value = query[1];

            if (operation == 0) {
                sortedSet.add(value);
                results.add(sortedSet.size());
            } else if (operation == 1) {
                sortedSet.remove(value);
                results.add(sortedSet.size());
            } else if (operation == 2) {
                Integer result = sortedSet.ceiling(value);
                if (result != null) {
                    results.add(result);
                } else {
                    results.add(-1);
                }
            }
        }
        return results;
    }

    public static void main(String[] args) {
        List<int[]> queries = Arrays.asList(
            new int[]{0, 10},
            new int[]{2, 10},
            new int[]{0, 20},
            new int[]{1, 10},
            new int[]{2, 10}
        );

        List<Integer> result = processQueries(queries);
        for (int res : result) {
            System.out.print(res + " ");
        }  // Output: 1 10 2 1 20
    }
}

import java.util.*;

public class EfficientQueries {
    public static List<Integer> processQueries(List<int[]> queries) {
        TreeSet<Integer> sortedSet = new TreeSet<>();
        List<Integer> results = new ArrayList<>();

        for (int[] query : queries) {
            int operation = query[0];
            int value = query[1];

            if (operation == 0) {
                sortedSet.add(value);
                results.add(sortedSet.size());
            } else if (operation == 1) {
                sortedSet.remove(value);
                results.add(sortedSet.size());
            } else if (operation == 2) {
                Integer result = sortedSet.ceiling(value);
                if (result != null) {
                    results.add(result);
                } else {
                    results.add(-1);
                }
            }
        }
        return results;
    }

    public static void main(String[] args) {
        List<int[]> queries = Arrays.asList(
            new int[]{0, 10},
            new int[]{2, 10},
            new int[]{0, 20},
            new int[]{1, 10},
            new int[]{2, 10}
        );

        List<Integer> result = processQueries(queries);
        for (int res : result) {
            System.out.print(res + " ");
        }  // Output: 1 10 2 1 20
    }
}