Counting Alternating Groups in a Circular Array - Java - 2 ms beats 100% - 66 mb beats 98%
Intuition\nThe problem involves counting groups of alternating colors in a circular array, where the array can be updated dynamically. The challenge lies in eff
# Intuition\nThe problem involves counting groups of alternating colors in a circular array, where the array can be updated dynamically. The challenge lies in efficiently counting these alternating groups and handling updates without recalculating everything from scratch.\n\nGiven the circular nature and the need for efficient updates, we recognize that a straightforward approach could involve excessive recomputation. Instead, we can leverage a BitSet to track transitions between colors and efficiently calculate the number of groups based on these transitions.\n\n# Approach\n1. Representation of Colors:\nWe first create an adjusted array of colors where each color is XORed with its index\'s parity (even/odd). This helps in simplifying the problem by turning it into a linear (non-circular) problem.\n\n2. BitSet for Transition Tracking:\nWe use a BitSet to track the positions where the color changes occur (transitions). This allows us to quickly determine the start and end of alternating groups.\n\n3. Frequency Array:\nWe maintain a frequency array that keeps track of the length of these alternating groups. Another BitSet helps us manage which group lengths are currently present.\n\n4. Processing Queries:\nFor each query, if it\'s an update operation, we adjust the BitSet and frequency array accordingly.\nIf it\'s a query for counting alternating groups of a specific length, we compute the result by summing up the relevant group counts.\n\n5. Handling Circular Nature:\nThe circular property of the array is handled by creating a virtual doubled array and ensuring that the transition tracking and frequency calculations are appropriately adjusted.\n\n# Complexity\n- Time complexity:The initialization takes O(n), where n is the length of the array. Each query (whether an update or a counting operation) takes O(logn) in the worst case due to the operations on the BitSet.\n- Space complexity:O(n), primarily due to the storage for the adjusted color array, the BitSet, and the frequency array.\n\n\n# Code\n```java []\nimport java.util.AbstractList;\nimport java.util.ArrayList;\nimport java.util.List;\n\nclass Solution {\n\n    public List<Integer> numberOfAlternatingGroups(int[] colors, int[][] queries) {\n        return new AbstractList<Integer>() {\n\n            private List<Integer> resultList;\n\n            private void initialize() {\n                resultList = new ArrayList<>();\n\n                int length = colors.length;\n                int[] adjustedColors = new int[2 * length];\n                for (int i = 0; i < 2 * length; i++) {\n                    adjustedColors[i] = colors[i % length] ^ (i % 2 == 0 ? 0 : 1);\n                }\n\n                BitSet bitSet = new BitSet(2 * length + 3);\n                for (int i = 1; i < 2 * length; i++) {\n                    if (adjustedColors[i] != adjustedColors[i - 1]) {\n                        bitSet.set(i);\n                    }\n                }\n\n                int[] frequency = new int[2 * length + 1];\n                BitSet frequencySet = new BitSet(2 * length + 1);\n                for (int i = 0; i < length; i++) {\n                    if (bitSet.get(i)) {\n                        int nextIndex = bitSet.next(i + 1);\n                        if (nextIndex == -1) {\n                            nextIndex = 2 * length;\n                        }\n                        frequency[nextIndex - i]++;\n                        frequencySet.set(nextIndex - i);\n                    }\n                }\n\n                for (int[] query : queries) {\n                    if (query[0] == 1) {\n                        if (bitSet.next(0) == -1) {\n                            resultList.add(length);\n                        } else {\n                            int count = 0;\n                            for (int i = frequencySet.next(query[1]); i != -1; i = frequencySet.next(i + 1)) {\n                                count += (i - query[1] + 1) * frequency[i];\n                            }\n                            if (adjustedColors[2 * length - 1] != adjustedColors[0]) {\n                                int firstIndex = bitSet.next(0);\n                                if (firstIndex >= query[1]) {\n                                    count += (firstIndex - query[1] + 1);\n                                }\n                            }\n\n                            resultList.add(count);\n                        }\n                    } else {\n                        int index = query[1];\n                        int newValue = query[2];\n                        if (colors[index] == newValue) {\n                            continue;\n                        }\n                        colors[index] ^= 1;\n                        update(index, bitSet, frequency, length, frequencySet, adjustedColors);\n                        update(index + length, bitSet, frequency, length, frequencySet, adjustedColors);\n                    }\n                }\n            }\n\n            private void update(int index, BitSet bitSet, int[] frequency, int length, BitSet frequencySet, int[] adjustedColors) {\n                if (index > 0) {\n                    int previousIndex = bitSet.prev(index - 1);\n                    int nextIndex = bitSet.next(previousIndex + 1);\n                    if (nextIndex == -1) {\n                        nextIndex = 2 * length;\n                    }\n                    if (previousIndex != -1 && previousIndex < length && --frequency[nextIndex - previousIndex] == 0) {\n                        frequencySet.unset(nextIndex - previousIndex);\n                    }\n                }\n                if (bitSet.get(index)) {\n                    int previousIndex = index;\n                    int nextIndex = bitSet.next(index + 1);\n                    if (nextIndex == -1) {\n                        nextIndex = 2 * length;\n                    }\n                    if (previousIndex != -1 && previousIndex < length && --frequency[nextIndex - previousIndex] == 0) {\n                        frequencySet.unset(nextIndex - previousIndex);\n                    }\n                }\n                if (bitSet.get(index + 1)) {\n                    int previousIndex = index + 1;\n                    int nextIndex = bitSet.next(index + 2);\n                    if (nextIndex == -1)\n                        nextIndex = 2 * length;\n                    if (previousIndex != -1 && previousIndex < length && --frequency[nextIndex - previousIndex] == 0) {\n                        frequencySet.unset(nextIndex - previousIndex);\n                    }\n                }\n                bitSet.unset(index);\n                bitSet.unset(index + 1);\n                adjustedColors[index] ^= 1;\n                if (index > 0 && adjustedColors[index] != adjustedColors[index - 1]) {\n                    bitSet.set(index);\n                }\n                if (index + 1 < adjustedColors.length && adjustedColors[index + 1] != adjustedColors[index]) {\n                    bitSet.set(index + 1);\n                }\n\n                if (index > 0) {\n                    int previousIndex = bitSet.prev(index - 1);\n                    int nextIndex = bitSet.next(previousIndex + 1);\n                    if (nextIndex == -1)\n                        nextIndex = 2 * length;\n                    if (previousIndex != -1 && previousIndex < length && ++frequency[nextIndex - previousIndex] == 1) {\n                        frequencySet.set(nextIndex - previousIndex);\n                    }\n                }\n                if (bitSet.get(index)) {\n                    int previousIndex = index;\n                    int nextIndex = bitSet.next(index + 1);\n                    if (nextIndex == -1)\n                        nextIndex = 2 * length;\n                    if (previousIndex != -1 && previousIndex < length && ++frequency[nextIndex - previousIndex] == 1) {\n                        frequencySet.set(nextIndex - previousIndex);\n                    }\n                }\n                if (bitSet.get(index + 1)) {\n                    int previousIndex = index + 1;\n                    int nextIndex = bitSet.next(index + 2);\n                    if (nextIndex == -1)\n                        nextIndex = 2 * length;\n                    if (previousIndex != -1 && previousIndex < length && ++frequency[nextIndex - previousIndex] == 1) {\n                        frequencySet.set(nextIndex - previousIndex);\n                    }\n                }\n            }\n\n            private void init() {\n                if (resultList == null) {\n                    initialize();\n                    System.gc();\n                }\n            }\n\n            @Override\n            public Integer get(int index) {\n                init();\n                return resultList.get(index);\n            }\n\n            @Override\n            public int size() {\n                init();\n                return resultList.size();\n            }\n\n        };\n\n    }\n\n    public static class BitSet {\n        private long[][] set;\n        private int size;\n\n        public BitSet(int size) {\n            this.size = size;\n            int depth = 1;\n            for (int m = size; m > 1; m >>>= 6, depth++)\n                ;\n\n            set = new long[depth][];\n            for (int i = 0, m = size >>> 6; i < depth; i++, m >>>= 6) {\n                set[i] = new long[m + 1];\n            }\n        }\n\n        public BitSet setRange(int range) {\n            for (int i = 0; i < set.length; i++, range = range + 63 >>> 6) {\n                for (int j = 0; j < range >>> 6; j++) {\n                    set[i][j] = -1L;\n                }\n                if ((range & 63) != 0) {\n                    set[i][range >>> 6] |= (1L << range) - 1;\n                }\n            }\n            return this;\n        }\n\n        public BitSet unsetRange(int range) {\n            if (range >= 0) {\n                for (int i = 0; i < set.length; i++, range = range + 63 >>> 6) {\n                    for (int j = 0; j < range + 63 >>> 6; j++) {\n                        set[i][j] = 0;\n                    }\n                    if ((range & 63) != 0) {\n                        set[i][range >>> 6] &= -(1L << range);\n                    }\n                }\n            }\n            return this;\n        }\n\n        public BitSet set(int position) {\n            if (position >= 0 && position < size) {\n                for (int i = 0; i < set.length; i++, position >>>= 6) {\n                    set[i][position >>> 6] |= 1L << position;\n                }\n            }\n            return this;\n        }\n\n        public BitSet unset(int position) {\n            if (position >= 0 && position < size) {\n                for (int i = 0; i < set.length && (i == 0 || set[i - 1][position] == 0L); i++, position >>>= 6) {\n                    set[i][position >>> 6] &= ~(1L << position);\n                }\n            }\n            return this;\n        }\n\n        public boolean get(int position) {\n            return position >= 0 && position < size && set[0][position >>> 6] << ~position < 0;\n        }\n\n        public BitSet toggle(int position) {\n            return get(position) ? unset(position) : set(position);\n        }\n\n        public int prev(int position) {\n            for (int i = 0; i < set.length && position >= 0; i++, position >>>= 6, position--) {\n                int previous = prev(set[i][position >>> 6], position & 63);\n                if (previous != -1) {\n                    position = position >>> 6 << 6 | previous;\n                    while (i > 0)\n                        position = position << 6 | 63 - Long.numberOfLeadingZeros(set[--i][position]);\n                    return position;\n                }\n            }\n            return -1;\n        }\n\n        public int next(int position) {\n            for (int i = 0; i < set.length && position >>> 6 < set[i].length; i++, position >>>= 6, position++) {\n                int next = next(set[i][position >>> 6], position & 63);\n                if (next != -1) {\n                    position = position >>> 6 << 6 | next;\n                    while (i > 0)\n                        position = position << 6 | Long.numberOfTrailingZeros(set[--i][position]);\n                    return position;\n                }\n            }\n            return -1;\n        }\n\n        private static int prev(long set, int n) {\n            long h = set << ~n;\n            if (h == 0L) {\n                return -1;\n            }\n            return -Long.numberOfLeadingZeros(h) + n;\n        }\n\n        private static int next(long set, int n) {\n            long h = set >>> n;\n            if (h == 0L) {\n                return -1;\n            }\n            return Long.numberOfTrailingZeros(h) + n;\n        }\n\n        @Override\n        public String toString() {\n            List<Integer> list = new ArrayList<>();\n            for (int pos = next(0); pos != -1; pos = next(pos + 1)) {\n                list.add(pos);\n            }\n            return list.toString();\n        }\n    }\n}\n\n```
['Array', 'Binary Indexed Tree', 'Java']