An Interview Question: O(n) Algorithm to Find Abs(Max Left – Max Right)


Given an array of numbers (for simplicity, we use integers), find the maximum value of abs(max left – max right) where we separate the array into two. Mathematically, given a[0] to a[n – 1] where n is the lenght of the array, we want to find out the following:

tex_643825e583f72d0718757bc3cfc2759e An Interview Question: O(n) Algorithm to Find Abs(Max Left - Max Right) c / c++ interview questions math

O(n) space and O(n) time

We can use two arrays e.g. maxleft and maxright to record the current maximum value from the left or right respectively. The third iteration goes from left to right to look for the maximum value of the difference.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int proof(int nums[], int n) {
    vector <int> maxleft(n);
    maxleft[0] = nums[0];
    for (int i = 1; i < n; ++ i) {
        maxleft[i] = max(maxleft[i - 1], nums[i]);
    }
    vector<int> maxright(n);
    maxright[n - 1] = nums[n - 1];
    for (int i = n - 2; i >= 0; -- i) {
        maxright[i] = max(maxright[i + 1], nums[i]);
    }
    int ans = abs(maxleft[0] - maxright[0]);
    for (int i = 1; i < n; ++ i) {
        ans = max(ans, abs(maxleft[i] - maxright[i]));
    }
    return ans;
}
int proof(int nums[], int n) {
    vector <int> maxleft(n);
    maxleft[0] = nums[0];
    for (int i = 1; i < n; ++ i) {
        maxleft[i] = max(maxleft[i - 1], nums[i]);
    }
    vector<int> maxright(n);
    maxright[n - 1] = nums[n - 1];
    for (int i = n - 2; i >= 0; -- i) {
        maxright[i] = max(maxright[i + 1], nums[i]);
    }
    int ans = abs(maxleft[0] - maxright[0]);
    for (int i = 1; i < n; ++ i) {
        ans = max(ans, abs(maxleft[i] - maxright[i]));
    }
    return ans;
}

This C++ implementation is straightforward and we can also merge the second and the third iteration, which eventually makes O(2n) time and O(n) space. But could we do any better?

O(n) time and O(1) space

We can easily prove that maxleft and maxright is contionously incrementing and decrementing respectively. Also, we know that:

tex_cb3eccca5c1a1a5caa6dfe2f5f64974e An Interview Question: O(n) Algorithm to Find Abs(Max Left - Max Right) c / c++ interview questions math

So, the overall answer must be the max(a) minus the tex_ff130819e00087291945a84007248d45 An Interview Question: O(n) Algorithm to Find Abs(Max Left - Max Right) c / c++ interview questions math or tex_4d497561dcad6dbbc5a1b65fa811bfc0 An Interview Question: O(n) Algorithm to Find Abs(Max Left - Max Right) c / c++ interview questions math . This gives the O(n) time and O(1) space complexity.

1
2
3
4
5
6
7
int findme(int nums[], int n) {
    int ans = nums[0];
    for (int i = 1; i < n; ++ i) {
        ans = max(ans, nums[i]);
    }
    return max(ans - nums[0], ans - nums[n - 1]);
}
int findme(int nums[], int n) {
    int ans = nums[0];
    for (int i = 1; i < n; ++ i) {
        ans = max(ans, nums[i]);
    }
    return max(ans - nums[0], ans - nums[n - 1]);
}

For example:

1
2
3
int nums[] = {2, 3, 6, 9, 11, 99, 88, 66, 1991, 3, 5, 22, 1, 2, 34, 6, 4, 5, 324, 5, 99};
cout << proof(nums, sizeof(nums) / sizeof(int)) << endl; // prints 1989
cout << findme(nums, sizeof(nums) / sizeof(int)) << endl; // prints 1989
int nums[] = {2, 3, 6, 9, 11, 99, 88, 66, 1991, 3, 5, 22, 1, 2, 34, 6, 4, 5, 324, 5, 99};
cout << proof(nums, sizeof(nums) / sizeof(int)) << endl; // prints 1989
cout << findme(nums, sizeof(nums) / sizeof(int)) << endl; // prints 1989

PS: We don’t want any sorting involved, because it at least is of complexity O(nlogn) for any sorting techniques.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
613 words
Last Post: C++ whereis for Windows
Next Post: How to Fix Microsoft PowerPoint Attempting-to-Repair-but-Fail Problem? (cannot open)

The Permanent URL is: An Interview Question: O(n) Algorithm to Find Abs(Max Left – Max Right)

2 Comments

  1. div1user

Leave a Reply