CSES Traffic Lights TLE

Hi, I am working on this problem https://cses.fi/problemset/task/1163/. My idea is basically to process the traffic lights in reverse order. First, I will find the max gap when all traffic lights are placed. Then, one by one in reverse order (of the input), I will use the ceiling/floor function of the TreeSet to see the size of the new gap that has opened up after I remove this current traffic light. Then, I compare it with the previous max answer, and I will only keep the max.

However, I am getting TLE on the last 7 cases, AC the first 5. I don’t know if it is because Java is too slow for this problem, because that has happened to me before.

import java.io.*;
import java.util.*;
class cses {
    static int n;
    static int m;
    public static void main(String[] args) throws IOException{
        BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(file.readLine());
        int x = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        TreeSet<Integer> set = new TreeSet<>();
        int[] arr = new int[n];
        st = new StringTokenizer(file.readLine());
        for (int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        int ans = 0;
        int prev = 0;
        for (int curr : set){
            ans = Math.max(ans, curr-prev);
            prev = curr;
        int[] out = new int[n];
        out[n-1] = ans;
        for (int i=n-1; i>0; i--){
            int curr = arr[i];
            ans = Math.max(set.ceiling(curr)-set.floor(curr), ans);
            out[i-1] = ans;
        for (int i : out){
            System.out.print(i + " ");

Maybe try printing out it all as one string with StringBuilder? If that doesn’t work, you might need fast input as well: https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/

It’s possible TreeSet is also sort of slow, this problem can be done with linkedlists as well (implement your own double linkedlist on an array).

Maybe you should try writing this code in C++. Unlike USACO and CF, some CSES problems tend to time out with Java. Based on your time complexity, you seem to have a passing solution. Therefore, the only possible reason why you would get TLE is because you’re using Java…


try submitting on the cf gym?

1 Like

Yea, this works.