C++ | 0 ms | Beats 100% | O(n) | Step By Step Explained 🚀
Intuition\n Describe your first thoughts on how to solve this problem. \nThe algorithm uses two pointers, or positions, in the array to compare elements effecti
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe algorithm uses two pointers, or positions, in the array to compare elements effectively. We decided to use two pointers because it helps us easily check each pair of adjacent elements in the array. This approach simplifies the process of finding the maximum difference between two elements by systematically examining each possible pair.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialization:\nn = nums.size(): Get the size of the input vector nums.\nCheck if the size of the array is less than 2. If so, it means there are not enough elements in the array to find a difference, so return -1.\n2. Variables Initialization:\nmaxDiff = -1: Initialize the variable maxDiff to store the maximum difference between two elements.\nleft = 0, right = 1: Initialize two pointers left and right pointing to the first and second elements of the array, respectively.\n3. Iterating through the Array:\n- Start a while loop iterating over the array elements starting from the second element (right = 1) until reaching the end of the array.\n- Inside the loop, compare the element at index left with the element at index right.\n- - If nums[left] < nums[right], it means the element at right is larger than the element at left. Calculate the difference (nums[right] - nums[left]) and update maxDiff if this difference is greater than the current maxDiff.\n-  - Increment right to move to the next element.\n- - If nums[left] >= nums[right], it means the element at right is not greater than the element at left, so update left to right and move right to the next element.\n- - This is done, as values from left to right are increasing(that is why we were able to calculate the difference). So, any value between left and right will be greater than the value from nums[left] so left is updated to right.\n4. Return Result:\nOnce the loop completes, return the value of maxDiff, which represents the maximum difference found between two elements in the array where the larger element comes after the smaller element.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of this algorithm is O(n), where n is the size of the input array nums, because it iterates through the array only once.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is O(1), because the algorithm uses only a constant amount of extra space for storing variables irrespective of the size of the input array.\n\n# Code\n```\nclass Solution {\npublic:\n    int maximumDifference(vector<int>& nums) {\n        int n = nums.size();\n    if (n < 2)\n        return -1;\n\n    int maxDiff = -1;\n    int left = 0, right = 1;\n\n    while (right < n) {\n        if (nums[left] < nums[right]) {\n            maxDiff = max(maxDiff, nums[right] - nums[left]);\n            right++;\n        } else {\n            left = right;\n            right++;\n        }\n    }\n\n    return maxDiff;\n    }\n};\n```
['Array', 'C++']