SortedList and Binary Search
Approach\nBest possible approach might be using Segment Tree, but we attempt to do it here using SortedList and Binary Search.\n\n We hold a SortedList of all t
# Approach\nBest possible approach might be using Segment Tree, but we attempt to do it here using SortedList and Binary Search.\n\n* We hold a SortedList of all the obstacle indices and the max possible gap up to that point\n* We iterate over the queries list, and:\n  * If it is an obstacle, we add it to the SortedList and update the max Gap from that point and beyond.\n  * If it is a block, we do some basic checks to determine if a result could be determined without a search, and if not we find the nearest obstacle to the `x` range of the block and determine the max gap around it.\n\n# Complexity\n- Time complexity:\n  - PlaceObstacle would iterate over the obstacles list in worst case, so it would take O(n)\n  - TryPlaceBlock uses Binary Search, so it would take O(log n)\n\n  <br />\n  Overall: O(n + log(n))\n\n<br/>\n\n- Space complexity:\nO(n)\n\n# Code\n```\n// Best possible approach might be using Segment Tree\n// But we attempt to do it here using SortedList and Binary Search.\npublic class Solution\n{\n    private readonly SortedList<int, int> _obstaclesWithMaxGap = new SortedList<int, int>();\n\n    public IList<bool> GetResults(int[][] queries)\n    {\n        List<bool> results = new List<bool>();\n\n        foreach (int[] query in queries)\n        {\n            if (query[0] == 1)\n            {\n                // Handle obstacle\n                PlaceObstacle(query[1]);\n            }\n            else if (query[0] == 2)\n            {\n                // Check if block can be placed\n                bool result = TryPlaceBlock(query[2], query[1]);\n                results.Add(result);\n            }\n            else\n            {\n                throw new ArgumentException("Invalid query type received. Query type should be either 1 or 2");\n            }\n        }\n\n        return results;\n    }\n\n    private void PlaceObstacle(int x)\n    {\n        _obstaclesWithMaxGap.Add(x, x);\n\n        // Update max gap of recently added obstacle\n        int indexOfObstacle = _obstaclesWithMaxGap.IndexOfKey(x);\n        if (indexOfObstacle > 0)\n        {\n            int previousObstacle = _obstaclesWithMaxGap.Keys[indexOfObstacle - 1];\n            int currentMaxGap = _obstaclesWithMaxGap.Values[indexOfObstacle - 1];\n            _obstaclesWithMaxGap[x] = Math.Max(currentMaxGap, x - previousObstacle);\n        }\n        for (int i = indexOfObstacle + 1; i < _obstaclesWithMaxGap.Count; i++)\n        {\n            int newMax = Math.Max(_obstaclesWithMaxGap.Values[i - 1], _obstaclesWithMaxGap.Keys[i] - _obstaclesWithMaxGap.Keys[i - 1]);\n            if (_obstaclesWithMaxGap.Values[i] != newMax)\n            {\n                _obstaclesWithMaxGap.SetValueAtIndex(i, newMax);\n            }\n            else\n            {\n                // If the previous gap is already the max gap, then no need to update further - this is an important optimization\n                break;\n            }\n        }\n    }\n\n    private bool TryPlaceBlock(int size, int maxX, int startingIndex = 0)\n    {\n        if (startingIndex + size > maxX)\n        {\n            return false;\n        }\n\n        if (!_obstaclesWithMaxGap.Any())\n        {\n            // first obstacle is beyond range - block can be added\n            return true;\n        }\n\n        // It is important to not use First() and Last() methods of SortedList as they are O(n) operations and will cause an iteration over the list\n        var firstObstacle = _obstaclesWithMaxGap.Keys[0];\n        var lastObstacle = _obstaclesWithMaxGap.Keys[_obstaclesWithMaxGap.Count - 1];\n        var lastObstacleMaxGap = _obstaclesWithMaxGap.Values[_obstaclesWithMaxGap.Count - 1];\n        if (startingIndex == 0 && firstObstacle >= maxX)\n        {\n            return true;\n        }\n        else if (maxX < firstObstacle)\n        {\n            return maxX >= size;\n        }\n        else if (maxX > lastObstacle)\n        {\n            return lastObstacleMaxGap >= size || maxX - lastObstacle >= size;\n        }\n        else\n        {\n            int nearestObstacle = BinarySearchNearestObstacleFromX(maxX, lastObstacle);\n            if (nearestObstacle < maxX)\n            {\n                return _obstaclesWithMaxGap[nearestObstacle] >= size || maxX - nearestObstacle >= size;\n            }\n            else\n            { // nearestObstacle > maxX\n                return _obstaclesWithMaxGap[nearestObstacle] - (nearestObstacle - maxX) >= size;\n            }\n        }\n    }\n\n    private int BinarySearchNearestObstacleFromX(int x, int lastObstacle)\n    {\n        if (x >= lastObstacle)\n        {\n            return lastObstacle;\n        }\n\n        int start = 0;\n        int end = _obstaclesWithMaxGap.Count();\n        int middle = (start + end) / 2;\n\n        while (start <= end)\n        {\n            if (_obstaclesWithMaxGap.Keys[middle] == x)\n            {\n                return x;\n            }\n            else if (_obstaclesWithMaxGap.Keys[middle] < x)\n            {\n                start = middle + 1;\n            }\n            else\n            { // _obstaclesWithMaxGap.Keys[middle] > x\n                end = middle - 1;\n            }\n            middle = (start + end) / 2;\n        }\n\n        return _obstaclesWithMaxGap.Keys[middle];\n    }\n}\n```
['C#']