Java Binary Search O(nlogn) seat() O(1) leave() TLE
Haven\'t seen any other similar approaches using binary search.\nHeres a solution that tries to leverage the binary search approach, although it TLEs\n\nThe ide
Haven\'t seen any other similar approaches using binary search.\nHeres a solution that tries to leverage the binary search approach, although it TLEs\n\nThe idea here is we know the max distance between student is N - 1, and the min is 0,\nso we use binary search to optimally guess that optimal seat \n\nWe do this by making a guess and then running a O(N) sliding window to check if it\'s valid\n\n\n```\nclass ExamRoom {\n    boolean[] seats;\n    int seatsTaken = 0;\n    public ExamRoom(int N) {\n        seats = new boolean[N];\n    }\n    \n    public int seat() {\n        if (seatsTaken == 0) {\n            seats[0] = true;\n            seatsTaken++;\n            return 0;\n        }\n        if (seatsTaken == seats.length) {\n            return -1;\n        }\n        \n        int l = 0;\n        int r = seats.length - 1;\n        \n        int maxDistanced = 0;\n        while (l <= r) {\n            int m = l + (r - l) / 2;\n            int seat = validDistance(m);\n            if (seat != -1) {\n                maxDistanced = Math.max(seat, maxDistanced);\n                l = m + 1;\n            } else {\n                r = m - 1;\n            }\n            \n        }\n        seatsTaken++;\n        seats[maxDistanced] = true;\n        return maxDistanced;\n    }\n    // O(N) sliding window to determine if guessed spacing is valid\n    public int validDistance(int distance) {\n        int left = 0;\n        int right = 0;\n        int index = 0;\n        while (seats[index]) {\n            index++;\n        }\n        \n        for (int min = Math.max(0, index - distance); min < index; min++) {\n            if (seats[min]) {\n                left++;\n            }\n        }\n        \n        for (int max = Math.min(seats.length - 1, index + distance); max > index; max--) {\n            if (seats[max]) {\n                right++;\n            }\n        }\n        \n        if (left == 0 && right == 0) {\n            return index;\n        }\n        \n        \n        for (int i = index + 1; i < seats.length; i++) {\n            \n            if (i - distance - 1 >= 0 && seats[i - distance - 1]) left--;\n            if (seats[i - 1]) {\n                left++;\n                right--;\n            }\n            if (i + distance <= seats.length - 1 && seats[i + distance]) right++;\n            if (left == 0 && right == 0 && !seats[i]) {\n                return i;\n            }\n        }\n        \n        return -1;\n    }\n    \n    public void leave(int p) {\n        seats[p] = false;\n        seatsTaken--;\n    }\n}\n\n\n```
['Binary Search', 'Java']