4
\$\begingroup\$

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;
}
\$\endgroup\$
4
\$\begingroup\$

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)\$ as when considering such things we don't worry about multiples of N, so iterating through the list twice \$O(2n)\$ is, for complexity comparisons, the same as \$O(n)\$.

The bad news is that the algorithm is flawed.

  1. Find the largest number,
  2. 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;
}
\$\endgroup\$
  • \$\begingroup\$ Nicely put, but wouldn't it be better to not have prev and remove the else such that you use arr[i - 1] instead? This would work just fine because you start the loop at one. Also, you could change the loop to: for(int i = len - 1; i--;) then instead check against arr[i + 1] which is more of a personal preference:) \$\endgroup\$ – tkellehe Jun 24 '16 at 11:41
  • \$\begingroup\$ @AlanT - Thanks you much for the detailed feedback \$\endgroup\$ – oneday Jun 24 '16 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.