🎉BEATS 100%🏆| Most Efficient O(k log k + n) time🕒 No BinarySearch📈 Approach Explained🌟 | PHP
Intuition:\n- The idea is to select numbers in increasing order from 1 to n, ensuring:\n  - They are not banned.\n  - The total sum does not exceed maxSum.\n- B
# Intuition:\n- The idea is to select numbers in increasing order from `1` to `n`, ensuring:\n  - They are not banned.\n  - The total sum does not exceed `maxSum`.\n- By selecting smaller numbers first, we maximize the number of integers we can pick before the sum reaches the `maxSum`.\n\n# Approach :\n\n1. **Sort the `banned` array**:\n   - **Why?** Sorting the banned array helps in easier lookups later on, although in this solution, sorting is not directly necessary since we convert it into a hash table for fast lookups. The sorting step is technically redundant for efficiency, but it can help visualize or debug the solution.\n   \n2. **Convert the `banned` array into a set using `array_flip`**:\n   - The key insight here is that checking if a number is in the `banned` array can be made very fast if we use a **hash table** (or associative array in PHP).\n   - **Why `array_flip`?**:\n     - `array_flip(banned)` turns the banned array into an **associative array** where the values become the keys. This allows us to quickly check if a number is banned using `isset()`, which is much faster than `in_array()` (O(1) lookup instead of O(n)).\n\n3. **Iterate through numbers from `1` to `n`**:\n   - We want to pick the numbers in increasing order starting from 1. This ensures we can select as many numbers as possible without exceeding the `maxSum` by picking smaller numbers first.\n   \n4. **Skip banned numbers**:\n   - As we iterate over the numbers from `1` to `n`, if the current number `i` is found in the banned set (using `isset($banned[$i])`), we skip it.\n\n5. **Add numbers to the sum**:\n   - If the current number is not banned and adding it to the sum doesn\u2019t exceed `maxSum`, we:\n     - Add the number to the sum.\n     - Increment the count of selected numbers.\n   - If adding the number exceeds `maxSum`, we stop and return the current count of numbers selected, as we cannot select any more numbers.\n\n6. **Return the result**:\n   - If we finish the loop without exceeding `maxSum`, we return the count of numbers we were able to select.\n\n\n# Complexity:\n\n- **Time Complexity**: $$O(k log k + n)$$ , where `k` is the number of elements in the banned array and n is the number given.\n  - **Sorting the banned array** takes **O(k log k)**, where `k` is the number of elements in the banned array.\n  - **Converting to a hash table** using `array_flip()` takes **O(k)**.\n  - **Looping through the numbers from 1 to `n`** takes **O(n)**.\n  - Overall complexity is **O(k log k + n)**.\n  \n- **Space Complexity**: $$O(k)$$ , where `k` is the number of elements in the banned array \n  - The space complexity is mainly due to the storage of the banned numbers in the hash table, which takes **O(k)** space.\n  - Additionally, we use variables like `sum`, `count`, and `i`, which take constant space.\n  - Thus, the space complexity is **O(k)**.\n\n\n# Code\n```php []\nclass Solution {\n\n    /**\n     * @param Integer[] $banned\n     * @param Integer $n\n     * @param Integer $maxSum\n     * @return Integer\n     */\n    function maxCount($banned, $n, $maxSum) {\n        sort($banned);\n        $sum = $count = 0;\n        $i=1;\n        $banned = array_flip($banned);\n        while($i<=$n  ){\n            if(!isset($banned[$i])){\n                if($sum +$i <= $maxSum){\n                    $sum += $i;\n                    $count ++;\n                    // echo "$count -> $i -> $sum \\n";\n                }\n                else {\n                    return $count;\n\n                }\n            }\n            $i++;\n        }\n        return $count;\n    }\n}\n```
['Array', 'Hash Table', 'Greedy', 'PHP', 'Sorting']