2 Different Approach using Sorting and Priority Queue (Heaps)
First Approach Using Sorting \n# Intuition\nTo maximize the product (nums[i]\u22121)\xD7(nums[j]\u22121), you need to find the two largest numbers in the array 
# First Approach Using Sorting \n# Intuition\nTo maximize the product (nums[i]\u22121)\xD7(nums[j]\u22121), you need to find the two largest numbers in the array since subtracting 1 from a larger number will still result in a relatively large value. Sorting the array helps to easily identify the two largest numbers, and thus the desired product can be calculated using these two numbers.\n\n# Approach\n1. **Sort the Array :** Begin by sorting the array nums in ascending order. This will arrange the numbers such that the largest numbers are at the end of the array. \n2. **Identify the Two Largest Numbers :** After sorting, the two largest numbers in the array will be at the last two indices. Specifically, the largest number will be at nums[nums.size() - 1] and the second largest will be at nums[nums.size() - 2].\n3. **Calculate the Product :** Subtract 1 from each of these two largest numbers and then calculate their product.\n4. # Complexity\n- **Time complexity :** O(n*log(n))\nThe time complexity of this solution is O(n log n) due to the sorting operation, where n is the number of elements in the input vector.\n- **Space complexity :** O(1)\n# Code\n```\nint maxProduct(vector<int>& nums) {\n        sort(nums.begin(),nums.end());\n        return (nums[nums.size()-1]-1)*(nums[nums.size()-2]-1);\n    }\n```\n---\n---\n---\n# Second Approach using Max Heap (Priority Queue)\n# Intuition\nThe maximum value of (nums[i]\u22121)\u2217(nums[j]\u22121) is achieved when nums[i] and nums[j] are the two largest numbers in the array. By using a max-heap (priority queue), we can efficiently extract these two largest numbers. The code pushes all elements into the heap, extracts the largest, then the second largest, and computes the product of their decrements.\n\n# Approach\n1. **Initialize a Max-Heap :** Use a max-heap (priority queue) to store all the elements of the array. This allows efficient retrieval of the largest elements. \n2. **Insert Elements :** Iterate over the array and push each element into the max-heap.\n3. **Extract the Largest Element :** Extract the largest element from the max-heap, which represents the maximum value in the array. Let\'s call this value x.\n4. **Remove the Largest Element :**Pop the largest element from the max-heap to access the second largest element.\n5. **Extract the Second Largest Element :** Extract the next largest element from the max-heap (that is pq.top()).\n6. **Compute the Result :** Calculate the product (x\u22121)\xD7(secondlargest\u22121) and return this value as the result.\n\n# Complexity\n- **Time complexity :** O(n*log(n))\nThe time complexity of this solution is O(n log n) where n is the number of elements in the input vector. This is because we are iterating through each element in the vector to insert it into the priority queue, which has a time complexity of O(log n) for each insertion. Additionally, we are performing two pop operations on the priority queue, each with a time complexity of O(log n).\n- **Space complexity :** O(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int maxProduct(vector<int>& nums) {\n        priority_queue<int> pq;\n        for(int i  : nums) pq.push(i);\n        int x=pq.top();\n        pq.pop();\n        return (x-1)*(pq.top()-1);\n    }\n};\n```
['Array', 'Sorting', 'Heap (Priority Queue)', 'C++']