Java | O(n*31) time | Slide Backwards | In-depth Easy Explanation with Example
Let\'s take the example of nums = [6,2,1,3,0]\nIn binary notation, we have:\nindex - value - binary notation\n0 - 6 - 110\n1 - 2 - 010\n2 - 1 - 001\n3 - 3 - 011
Let\'s take the example of nums = [6,2,1,3,0]\nIn binary notation, we have:\nindex - value - binary notation\n0 - 6 - 110\n1 - 2 - 010\n2 - 1 - 001\n3 - 3 - 011\n4 - 0 - 000\n\nWe can get the maximum bitwise or value for each index by looping from end to start:\n0 - 7 (111) = 0 | 3 | 1  | 2 | 6\n1 - 3 (011) = 0 | 3 | 1  | 2\n2 - 3 (011) = 0 | 3 | 1\n3 - 3 (011) = 0 | 3 \n0 - 0 (000) = 0\n\nAn initial idea is to, for each index, loop from the index to the end of the array to find the minimum length yielding the value, but that is O(n^2) time, which is the brute-force approach. We want something better.\n\nAnother way of looking at the problem is to look at how the bits get set when iterating from a specific index ```i``` to  ```n-1``` (where ```n == nums.length```). Looking at nums:\nFor index 0 (110), it has to reach index 2 (001) in order to get the rightmost bit set.\n=> smallest subarray for index 0 is length 2 - 0 + 1 = 3\n\nFor index 1 (010), it has to reach index 2 (001) in order to get the rightmost bit set.\n=> smallest subarray for index 1 is length 2 - 1 + 1 = 2\n\nFor index 2 (001), it has to reach index 3 (010) in order to get the 2nd rightmost bit set.\n=> smallest subarray for index 1 is length 3 - 2 + 1 = 2\n\nFor index 3 (011), it has to reach index 3 (011) in order to both the 1st and 2nd rightmost bit set.\n=> smallest subarray for index 1 is length 3 - 3 + 1 = 1\n\nFor index 4 (000), it has no indices to reach.\n=> smallest subarray for index 1 is length 3 - 3 + 1 = 1\n\nWe can then tabulate these "furthest indices" by iterating from ```n-1``` to ```0``` and by using array ```store``` to track them. ```store``` has size 31 since each array element represents a binary digit. We update store at index ```j``` on the iteration for index ```i``` when the jth rightmost binary digit of ```nums[i]``` is set (We\'ll just show the first three elements of ```store``` here for simplicity):\ni - nums[i] - store[0] store[1] store[2]\ni = 4 (nums[4] = 000): -1 -1 -1\ni = 3 (nums[3] = 011): 3 3 -1\ni = 2 (nums[2] = 001): 2 3 -1\ni = 1 (nums[1] = 010): 2 1 -1\ni = 0 (nums[0] = 110): 2 0 0\n\nAt iteration ```i```, max(store[0], ..., store[30]) then yields the furthest index we need to reach in order to get the max value.\nmax(store[0], ..., store[30]) - i + 1 then yields the minimum length needed.\nAn exception to this is when ```store[0] == ... == store[30] == -1```, then we set the minimum length to 1, since this only happens when the array is full of zeros from index ```i``` onwards.\nFor the example:\ni = 4: -1 (-1 means no bits have been set, we don\'t need nums[j] with j > i to set bits => min length = 1)\ni = 3: 3 (=> min length = 3 - 3 + 1 = 1)\ni = 2: 3 (=> min length = 3 - 2 + 1 = 2)\ni = 1: 2 (=> min length = 2 - 1 + 1 = 2)\ni = 0: 2 (=> min length = 2 - 0 + 1 = 3)\n\nFinally we put all of the above into some Java code:\n```\nclass Solution {\n    public int[] smallestSubarrays(int[] nums) {\n        int n = nums.length;\n        int[] ans = new int[n];\n        \n        int[] store = new int[31];\n        Arrays.fill(store, -1);\n        for(int i = n-1; i >= 0; --i){\n            int temp = nums[i];\n            for(int j = 0; j < 31; ++j){\n                if((temp & 1) == 1){\n                    store[j] = i;\n                }\n                temp >>= 1;\n            }\n            \n            int maxVal = Integer.MIN_VALUE;\n            for(int val: store){\n                maxVal = Math.max(maxVal, val);\n            }\n            if(maxVal == -1){\n                ans[i] = 1;\n            }else{\n                ans[i] = maxVal - i + 1;    \n            }\n        }\n        return ans;\n    }\n}\n```
['Bit Manipulation', 'Sliding Window', 'Java']