O(n + m) solution that is probably too complex
Intuition\n Describe your first thoughts on how to solve this problem. \nI tried to do clever stuff but it just kept adding complexity, so I had to add other cl
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nI tried to do clever stuff but it just kept adding complexity, so I had to add other clever stuff to deal with that complexity.\n\nSurprisingly, it actually passed on the second submission!\n\n---\n\n\n\nBasically the algorithm attempts to look at all numbers in the range 1 to nums.Max() and determine what the largest result is between two numbers:\n\nThe prefix of numbers in a row before a given number that can be shifted to the right by 1, plus the suffix of non-shifted numbers in a row at the given number + 1.\n\nThe prefix of numbers directly in a row prior to the given number, plus the suffix of non-shifted numbers in a row starting at the given number.\n\nWe perform these two calculations for every index i where:\n1 <= i <= nums.Max()\nand we save the largest result in a variable "maxInRow".\n\nThese two calculations represent forming contiguous sequences of numbers.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nThe maximum value of nums[i] (m) is less than 10^6, which means we can use a counting-sort style array to "sort" the array in O(n) time. By sort, I really just mean creating and populating the counting sort array.\n\nAfter creating and populating the counting sort array, I had this thought:\n"What if to start, I take any element that has 2 or more instances and shift 1 of them to the next spot?"\n\nThis seemed reasonable, but I figured out that it would interfere with the ability to determine what the longest prefix that can be shifted to the right is later on. So I needed to create an additional boolean array that would keep track of if a number has the ability to shift to the right or not.\n\nThis boolean array:\n```\nbool[] canShift = new bool[maxNum + 1];\n```\n\nis what I used for that.\n\n**So when can\'t an element shift?**\n\nAn element cannot be shifted to the right if either:\nA. There is no element in that current spot (count of numCount[i] is 0)\nOR\nB. There is only 1 element in the spot and it was donated by i - 1 (meaning it already performed it\'s +1 shift).\n\n\n\nAfter spreading out the numbers and marking which spots cannot be shifted further to the right, I initialize and fill the suffixNonShift array.\nThe suffixNonShift array is meant to be an array that at suffixNonShift[i] will store the longest contiguous sequence of characters that can be formed from the numbers in nums, with no more shifts, and with the first number being i. This is calculated via a simple suffix-sum operation:\n\n```c#\nfor (int i = maxNum; i > 0; i--){\n    if (numCount[i] > 0){\n        currInRow++;\n    }\n    else currInRow = 0;\n\n    suffixNonShift[i] = currInRow;\n}\n```\n\n***\n\n# Core-Algorithm\n\nThe core algorithm maintains two crucial variables:\n```c#\nint prefYesShift = 0;\nint prevInRow = 0;\n```\n\nprefYesShift - the number of elements in a row prior to i that can be shifted 1 to the right.\nprevInRow - the number of elements in a row prior to i.\n\nprefYesShift will be used to simulate shifting a group of numbers from the left, such that the last number in that group now sits at i. We will merge that section with the suffixNonShift sequence which starts at i + 1.\n\nprevInRow will be used to simulate merging a sequence of characters that ends just before i, with the suffixNonShift value located at i.\n\n\nFor each index i, from 1 to maxNum, we perform these imaginary mergers and store the maximum length of a sequence formed in this manner.\nThe final challenge is:\n\n**How do we maintain prevInRow and prefYesShift during the loop?**\n\nHere\'s what I came up with:\n```c#\nif (numCount[i] == 0){\n    prevInRow = prefYesShift;\n}\nelse prevInRow++;\nif (numCount[i] > 0 && canShift[i]){\n    prefYesShift++;\n}\nelse prefYesShift = 0;\n```\n\nThe logic is that IF we cannot naturally continue our prevInRow chain with no shifts, then prevInRow must become the result of shifting the numbers accounted for by prefYesShift to the right by 1.\n\nThen for each index i, if there exists at least 1 number with the value i, and that number hasn\'t been shifted yet (canShift[i] == true), then we can increment our prefYesShit variable by 1. Otherwise, the chain of contiguous shiftable numbers has been broken and we must reset prefYesShift to 0.\n\n# Complexity\n- Time complexity:$$O(n + m)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\nWhere n is the length of nums, and m is the maximum number in nums. We perform an O(n) operation to fill numCount, an O(m) operation to fill suffixNonShift, and an O(m) operation to calculate the maximum length of a contiguous sequence.\n\nO(n + m + m) == O(n + 2m) == O(n + m)\n\n- Space complexity: O(m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nWe require three data structures of size m + 1 for numCount, canShift, and suffixNonShift. O(3m + 3) == O(m).\n\n# Code\n```\npublic class Solution {\n    public int MaxSelectedElements(int[] nums) {\n        int maxNum = nums.Max() + 1;\n        int[] numCount = new int[maxNum + 1];\n        bool[] canShift = new bool[maxNum + 1];\n        Array.Fill(canShift, true);\n        foreach (var num in nums){\n            numCount[num]++;\n        }\n        for (int i = 1; i < maxNum; i++){\n            if (numCount[i] > 1){\n                numCount[i + 1]++;\n                numCount[i]--;\n\n                if (numCount[i + 1] == 1) canShift[i + 1] = false;\n            }\n            else if (numCount[i] == 0) canShift[i] = false;\n        }\n        canShift[0] = false;\n        int[] suffixNonShift = new int[maxNum + 1];\n\n        int currInRow = 0;\n        int maxInRow = 1;\n        for (int i = maxNum; i > 0; i--){\n            if (numCount[i] > 0){\n                currInRow++;\n            }\n            else currInRow = 0;\n\n            suffixNonShift[i] = currInRow;\n        }\n        int prefYesShift = 0;\n        int prevInRow = 0;\n\n        for (int i = 1; i <= maxNum; i++){\n            maxInRow = Math.Max(maxInRow, prevInRow + suffixNonShift[i]);\n            if (i != maxNum){\n                maxInRow = Math.Max(maxInRow, prefYesShift + suffixNonShift[i + 1]);\n            }\n            \n            if (numCount[i] == 0){\n                prevInRow = prefYesShift;\n            }\n            else prevInRow++;\n            if (numCount[i] > 0 && canShift[i]){\n                prefYesShift++;\n            }\n            else prefYesShift = 0;\n        }\n\n        return maxInRow;\n        \n    }\n}\n```
['Suffix Array', 'Prefix Sum', 'Counting Sort', 'C#']