Hi, recently I have attempted Leetcode Hard problem 3897. Maximum Value of Concatenated Binary Segments. After working on it for some time, I came up with a solution, but I ran into a Time Limit Exceeded (TLE) error on a specific test case.

Problem Overview

You are given two integer arrays nums1 and nums0, each of size n.

nums1[i] represents the number of '1's in the ith segment. nums0[i] represents the number of '0's in the ith segment. For each index i, construct a binary segment consisting of:

nums1[i] occurrences of '1' followed by nums0[i] occurrences of '0'. You may rearrange the order of these segments in any way. After rearranging, concatenate all segments to form a single binary string.

Return the maximum possible integer value of the concatenated binary string.

Since the result can be very large, return the answer modulo 109 + 7.

Constraints:

1 <= n == nums1.length == nums0.length <= 1e5

0 <= nums1[i], nums0[i] <= 1e4

nums1[i] + nums0[i] > 0

The total sum of all elements in nums1 and nums0 does not exceed 2 * 1e5.

My Approach and Solution

class Solution {
const long long MOD = 1e9+7;
public:
    int maxValue(vector<int>& nums1, vector<int>& nums0) {
        int n = nums1.size();
        auto b = vector<pair<int, int>>(n);

        auto pow2 = vector<long long>(200005);
        pow2[0] = 1;
        for (int i = 1; i < 200005; ++i) pow2[i] = 2 * pow2[i-1] % MOD;

        for (int i = 0; i < n; ++i) b[i] = {nums1[i], nums0[i]};
        std::sort(b.begin(), b.end(), [](const auto& a, const auto& b) {
            if (a.second == 0) return true;
            if (b.second == 0) return false;
            if (a.first > b.first) return true;
            if (b.first > a.first) return false;
            return a.second < b.second;   
        });

        long long res = 0;
        long long exp = 0;
        for (int i = n-1; i >= 0; --i) {
            auto& [n1, n0] = b[i];
            exp += n0;
            long long val = (pow2[exp] * ((pow2[n1] - 1LL + MOD) % MOD)) % MOD;
            res = (res + val) % MOD;
            exp += n1;
        }
        return res;
    }
};

I basically sort the segments in a greedy way to place as many ones at the front as possible to make the number as big as possible using the custom sort. Then I use the precomputed vector for the powers of two to compute the result of the number using MOD 1e9+7.

Time Complexity Analysis

Judging from the constraints, the length of nums1 and nums0 are 1e5, which means O(n^2) will cause TLE. So anything less should suffice.

My algorithm first places the values of nums1 and nums0 into vector b which is O(n). It then precomputes the power vector for 200005 values, I assume this can be thought of as O(1)? All the values in b are sorted using a custom sort which runs in O(1), thus implying that the sorting is O(nlogn). The final for loop iterates over n values to compute the result using the power vector, which is O(n) in total.

Therefore, the overall time complexity is O(nlogn) if I am not mistaken. This should be good enough for the constraints.

TLE Test Case

Based on this post, obviously my solution is too slow so I must be misunderstanding the time complexity analysis of my algorithm.

My solution TLEs on the following testcase: nums1 = [0,2252,1,10,0,1,453,1,3565,0,9984,5934,1327,836,1627,9368,472,7778,4752,103,1835,2,6309,5557,15,386,9755,8638,0,4935,2504,1,1,1,125,1,1]

nums0 = [1,1404,0,2,1,0,7574,0,388,1,8102,10000,7058,10000,7007,1889,3477,137,10000,1,10000,0,10000,4155,256,954,6552,2264,1,9767,104,0,0,0,375,0,0]

Questions

1. Why is my solution resulting in TLE on this specific test case, and probably many more?
2. What optimizations can I apply to improve the performance of my solution, how can I come across these optimisations intuitively (or do I just have to know them for the future)?
3. Are there any alternative approaches to solve this problem in a more efficient manner?

Thank you for reading my post. Any help and feedback is greatly appreciated. Thank you!