Problem

Can I get feedback on below code? Problem statement is Maximum difference between two elements such that larger element appears after the smaller number

Would this solution be still considered O(n) for time complexity? I know I do one additional pass but I found this way to be more intuitive

Is error handling done properly? Other ways to improve it?

```
int maxDiff(int *arr, int len);
int main(void)
{
int arr[] = {80, 2, 6, 3, 100};
int len = sizeof(arr)/sizeof(int);
int max_diff = maxDiff(arr, len);
printf(" max diff is %d n ", max_diff);
return 0;
}
int maxDiff(int *arr, int len)
{
int min = INT_MAX;
int max = INT_MIN;
int max_index;
if (len < 1 || arr == NULL)
{
printf(" No element present n ");
return INT_MIN;
}
for (int i = 0; i < len; i++)
{
if (arr[i] > max)
{
max = arr[i];
max_index = i;
}
}
for(int i = 0; i < max_index; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
}
return max - min;
}
```

Solution

**TestData**

I don’t know if the test data is given to you, but it is not the most useful for verifying the `such that larger element appears after the smaller number`

condition. Since 100 is the last value, any code that finds 100 as the largest number and subtracts the lowest number will find the *correct* answer. If the test data was

```
int arr[] = {100, 2, 6, 3, 80};
```

it would be a better test. The correct answer is now 78 because we ignore the 100 as it is before the 2.

**NOTE:** For the above data, the current code returns -2147483547 as the difference because we find 100 at the 0th element and never find a min value so the max difference is 100 – INT_MAX.

The code as written is O(n)$O(n)$ as when considering such things we don’t worry about multiples of N, so iterating through the list twice O(2n)$O(2n)$ is, for complexity comparisons, the same as O(n)$O(n)$.

The bad news is that the algorithm is flawed.

- Find the largest number,
- Find the largest difference between the largest number and all the numbers before it

fails if the largest number is first (as above), but also if there is a larger difference after the largest number

```
int arr[] = {50, 60, 100, 10, 70};
```

the code as written returns 50 but the correct answer 60 (70 – 10).

The following should give the correct answer.

```
#include <stdio.h>
int maxDiff(int* arr, int len);
int main(void)
{
int arr[] = { 50, 60, 100, 10, 70 };
int len = sizeof(arr) / sizeof(int);
int max_diff = maxDiff(arr, len);
printf(" max diff is %d n ", max_diff);
}
int maxDiff(int* arr, int len)
{
if (arr == NULL || len == 0)
{
return -1;
}
int prev = arr[0];
int maxDiff = 0;
for (int i = 1; i < len; ++i)
{
if (arr[i] > prev)
{
int newDiff = arr[i] - prev;
if (newDiff > maxDiff)
{
maxDiff = newDiff;
}
}
else
{
prev = arr[i];
}
}
return maxDiff;
}
```