Find All Unique Pairs of Maximum and Second Maximum Elements in Subarrays

Posted on Edited on In Disqus:

The root of the problem is that a classmate asked about a lucky number problem: Codeforces 280B. Codeforces 281D is the same problem.

Find all unique pairs of maximum and second maximum elements over all sub-arrays in O(NlogN)

A lucky number is defined as the XOR value of the maximum and second maximum of a subarray. The task is to find the largest lucky number among all lucky numbers.

The brute force solution enumerates all subarrays, with time complexity O(N ^ 2).
Is there a better method?
That is the problem to discuss today.

General Solution: Fast Algorithm for Finding Maximum and Second-Maximum Pairs

There is actually a fast algorithm for finding the maximum and second maximum in subarrays:
Find all unique pairs of maximum and second maximum elements over all sub-arrays in O(NlogN)

It is based on this observation: for each number in the array, if it wants to become the second maximum, it can only pair with the first number greater than it in front of it, or the first number greater than it after it.
We can maintain a monotonically decreasing stack. When adding a new number, to maintain monotonicity we pop all numbers smaller than it. At this time, the new number is the first number after the popped numbers that is greater than them; the largest number on the stack top is the first number before the new number that is greater than it.

Time complexity: O(N),
space complexity: O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <stack>
#include <vector>

using namespace std;
using ll = long long;

int solve() {
    ll N;
    cin >> N;
    vector<ll> nums(N);
    for (ll i = 0; i < N; ++i) {
        cin >> nums[i];
    }
    stack<ll> st;
    st.push(nums[0]);
    ll ans = 0;
    for (ll i = 1; i < N; ++i) {
        while (!st.empty() && nums[i] > st.top()) {
            ans = max(ans, nums[i] ^ st.top());
            st.pop();
        }
        if (!st.empty()) {
            ans = max(ans, nums[i] ^ st.top());
        }
        st.push(nums[i]);
    }
    return ans;
}

int main() {
    ll ans = solve();
    cout << ans << endl;
    return 0;
}

The Solution I Thought of Independently

My solution uses the property of XOR. If we replaced XOR with another operation, it would not be general.

First traverse once to find the highest bit.
Then traverse again to find the numbers whose highest bit is 1. Let us call them the highest numbers.
Starting from these highest numbers, expand to both sides until encountering another highest number. During this process, find the second maximum and update the maximum lucky number. It can be proven that each number is visited at most twice.
Therefore, the total time complexity is O(N), and the space complexity is O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

int solve() {
    int N;
    cin >> N;
    vector<ll> nums(N);
    for (ll i = 0; i < N; ++i) {
        cin >> nums[i];
    }
    const int MAX_BIT_BEGIN = 40;
    vector<vector<ll>> flag(MAX_BIT_BEGIN + 1, vector<ll>(2, 0));
    for (ll i : nums) {
        for (ll j = 0; j <= MAX_BIT_BEGIN; ++j) {
            ++flag[j][((i >> j) & 1)];
        }
    }
    ll max_bit = MAX_BIT_BEGIN;
    for (; max_bit >= 0; --max_bit) {
        if (flag[max_bit][0] > 0 && flag[max_bit][1] > 0) {
            break;
        }
    }
    if (max_bit == 0) {
        return 1;
    } else if (max_bit < 0) {
        return 0;
    } else {
        vector<ll> max_bit_is_1_indexs;
        for (ll i = 0; i < N; ++i) {
            if (((nums[i] >> max_bit) & 1) == 1) {
                max_bit_is_1_indexs.push_back(i);
            }
        }
        ll ans = 0;
        for (ll index : max_bit_is_1_indexs) {
            ll second_max = 0;
            for (ll i = index - 1; i >= 0 && ((nums[i] >> max_bit) & 1) == 0;
                 --i) {
                second_max = max(second_max, nums[i]);
                ans = max(ans, nums[index] ^ second_max);
            }
            second_max = 0;
            for (ll i = index + 1; i < N && ((nums[i] >> max_bit) & 1) == 0;
                 ++i) {
                second_max = max(second_max, nums[i]);
                ans = max(ans, nums[index] ^ second_max);
            }
        }
        return ans;
    }
}

int main() {
    ll ans = solve();
    cout << ans << endl;
    return 0;
}