O(n) time, using hash tables
Intuition\n Describe your first thoughts on how to solve this problem. \nThis is my second attempt and the goal is to avoid sorting or any operation that requir
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis is my second attempt and the goal is to avoid sorting or any operation that requires $n \\log n$ time.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe first identify the intervals of consecutive numbers. For each interval, the only important feature is if it contains duplicates, meaning at least a number appears at least twice.\nThis is done using hash tables.\n\nThe next step is to identify intervals between which the gap is 2.\nIf the gap were 1, then they would be merged into one interval at the previous step. If the gap is bigger than 2, then it is impossible to merge them using the allowed operations.\nSuch intervals with a gap of 2 can be chained (again using hash tables) and we examine each chain in reverse order, from highest to lowest.\nSeparate chains can be considered in arbitrary order. We can even alternate between chains, as long as each chain is handled in reverse order.\n\nFor each chain, the procedure is straightforward:\n* If an interval contains duplicates, we can glue it to the next-highest interval or extend it by 1 upward if it is the highest.\n* If an interval has no duplicates, then we leave it as it is or we can glue it to the next-higher interval in the chain, but either way the chain is broken and the larger glued interval cannot propagate downward.\n\nWe compare the lengths of all the maximal intervals obtained in this manner.\n\nSurprisingly, this solution is less fast than the [previous one](https://leetcode.com/problems/maximize-consecutive-elements-in-an-array-after-modification/solutions/4743924/one-pass-solution-specific-algorithm/) based on sorting.\n\n# Complexity\n- Time complexity: $O(n)$.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(n)$.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def maxSelectedElements(self, nums: List[int]) -> int:\n        dct=Counter(nums)\n        lst={}\n        for x in dct:\n            t=dct[x]\n            if t:\n                x0=x\n                flag=False\n                while t:\n                    if t>1:\n                        flag=True\n                    dct[x]=0\n                    if x+1 in dct:\n                        x+=1\n                        t=dct[x]\n                    else:\n                        t=1\n                        break\n                if t==0:\n                    b, f2=lst.pop(x)\n                    lst[x0]=(b, flag or f2)\n                else:\n                    lst[x0]=(x, flag)\n        lstx=[]\n        stx={x:True for x in lst.keys()}\n        for x in stx:\n            if stx[x]:\n                tmp=[x]\n                stx[x]=False\n                while True:\n                    b, _=lst[x]\n                    if b+2 in stx and stx[b+2]:\n                        x=b+2\n                        tmp.append(x)\n                        stx[x]=False\n                    else:\n                        break\n                lstx.extend(reversed(tmp))\n\n        ans=1\n        lst2={}\n\n        for x in lstx:\n            b, flag=lst[x]\n            if flag:\n                if b+2 in lst2:\n                    lst2[x]=lst2.pop(b+2)\n                else:\n                    lst2[x]=b+1\n            else:\n                if b+2 in lst2:\n                    ans=max(ans, lst2.pop(b+2)-x)\n                lst2[x]=b\n        \n        return max(ans, 1+max((b-x for x, b in lst2.items()), default=0))\n```
['Python3']