Simple and Fast 2-Step Java Solution with Sorting
Intuition\nTo compare some element to its adjascent elements, we can sort given input array.\n\n# Approach\n1. Sort input array.\n2. Iterate over sorted array a
# Intuition\nTo compare some element to its adjascent elements, we can sort given input array.\n\n# Approach\n1. Sort input array.\n2. Iterate over sorted array and check current element whether it is lonely or not using 4 conditions:\n- `prevEqual` **OR** `nextEqual` **OR** `prevSmaller` **OR** `nextBigger`\n\n# Complexity\n- **Time complexity:**\n`O(n)` in overall.\n\n**Details:**\n$$Step 1:$$ `O(n log n)` for sorting elements.\n$$Step 2:$$ `O(n)` for iterating over the sorted array.\nIn `big O`-notation the smallest part is ignored (step 1), therefore the overall time complexity is `O(n)`.\n\n- **Space complexity:**\n`O(n)` in overall.\n\n**Details:**\n$$Step 1:$$ Sorting array will take `O(log n)` space.\n$$Step 2:$$ Storing the lonely numbers in the `lonelyNumbers` list will take `O(n)` elements in the worst case (if all the numbers are lonely).\nTherefore space complexity is `O(n)` as we ignore the smallest part (step 1);\n\n\n# Code\n```\nclass Solution {\n    public List<Integer> findLonely(int[] nums) {\n        if (nums == null || nums.length == 0) {\n            return List.of();\n        }\n        Arrays.sort(nums);\n        List<Integer> lonelyNumbers = new ArrayList<>();\n        for (int i = 0; i < nums.length; i++) {\n            boolean prevEqual = (i - 1 >= 0 && nums[i] == nums[i - 1]);\n            boolean nextEqual = (i + 1 < nums.length && nums[i] == nums[i + 1]);\n            boolean prevSmaller = (i - 1 >= 0 && nums[i - 1] + 1 == nums[i]);\n            boolean nextBigger = (i + 1 < nums.length && nums[i + 1] == nums[i] + 1);\n            if (prevEqual || nextEqual || prevSmaller || nextBigger) {\n                continue; // not lonely number\n            }\n            lonelyNumbers.add(nums[i]);\n        }\n        return lonelyNumbers;\n    }\n}\n```
['Sorting', 'Java']