JAVA | With / without sorting | Explained ✅
---\n# Please Upvote \uD83D\uDE07\n---\n## 1. By sorting:\nWe want the maximum and second maximum as well as minimum and second minimum, difference of their pro
---\n# Please Upvote \uD83D\uDE07\n---\n## 1. By sorting:\nWe want the *maximum* and *second maximum* as well as *minimum* and *second minimum*, difference of their product will yield the maximum difference. \n\nWe will sort the array.\n- The max & the second max element will be found at the last and the second last indices of the array respectively.\n- The min and the second min element will be found at index `0` and index `1` respectively.\n\n#### Code:\n\n``` java []\nclass Solution {\n    public int maxProductDifference(int[] nums) {\n        Arrays.sort(nums);\n        int n = nums.length;\n        int ab = nums[0] * nums[1];\n        int cd = nums[n-1] * nums[n-2];\n        return cd - ab;     // return the product difference\n    }\n}\n\n// TC: , SC: O(1)\n```\n#### Time complexity: $$O(n * logn)$$\n#### Space complexity: $$O(1)$$\n---\n\n## 2. No sorting:\nWe will iterate through the array and get our max, second max, min and second min on the go using some simple conditions.\n\nLet\'s say we have an element `i`:\n1. If `i` is greater than `max`, `max` becomes `second max` and `i` becomes `max`.\n2. If `i` is greater than `second max` but smaller than `max`, `i` becomes `second max`.\n3. If `i` is smaller than `min`, `min` becomes `second min` and `i` becomes `min`.\n4. If `i` is smaller than `second min` but greater than `min`, `i` becomes `second min`.\n\n#### Code:\n``` java []\nclass Solution {\n    public int maxProductDifference(int[] nums) {\n        // given: 1 <= nums[i] <= 10000\n        int max = 0, max2 = 0;\n        int min = 10001, min2 = 10001;\n        for (int i : nums) {\n            if (i > max) {          // 1\n                max2 = max;\n                max = i;\n            } else if (i > max2) {  // 2\n                max2 = i;\n            }\n            if (i < min) {          // 3\n                min2 = min;\n                min = i;\n            } else if (i < min2) {  // 4\n                min2 = i;\n            }\n        }\n        // return the product difference\n        return max * max2 - min * min2; \n    }\n}\n```\n#### Time complexity: $$O(n)$$\n#### Space complexity: $$O(1)$$
['Sorting', 'Java']