LC 3202: XX, XY and YX. No, not the sex chromosomes!

Find the problem description here. If you would like to read the solution in leetcode platform, find it here.

---

Intuition

immediate intuition is that, we don't care about the actual numbers in the nums array. we just care about the remainders we will get when numbers are divided by the given k value. so, i first reduced all the numbers to their remainders.

why? because, modulo operator is associative. the remainder we get here: (a + b) % k is equal to the sum of a % k and b % k.

now, all we want are the pair-wise sums of these remainders. let us take two remainders X and Y. we want the sequences like this:

X X X X X ...
Y Y Y Y Y ...
X Y X Y X ...
Y X Y X Y ...

the first two are just the number of Xs and Ys present. the second two are the number of such pairs present.

we can use a 2D dp of array of dimensions k x k where k is the number of remainders we will get if the given value is k. here, dp[X][Y] represents the pair XY.

for every remainder, we will pair it with all the remaining possible remainders. the current can be equal to the running remainder. the current can start a pair ending with the running remainder. the current can end a pair starting with the running remainder.

---

Complexity

• Time complexity: $O(n * k + k^2)$. $k^2$ is for getting the maximum value.

• Space complexity: $O(k^2)$ for the 2D dp array.

---

Code

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int max_ = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            nums[i] %= k;
        }        

        // so here, i, j represents the seq i, j
        // we have i, j ranging from 0 to k - 1
        vector<vector<int>> dp(k, vector<int>(k, 0));

        for (int num : nums) {
            for (int i = 0; i < k; ++i) {
                if (i == num) {
                    dp[num][num]++;
                } else {
                    // (i, num). num is the second. so, if the pre length is odd, num ends the pair
                    if (dp[i][num] & 1)     dp[i][num]++;
                    // (num, i). num is the first. so, if the pre length is evem, num starts the pair
                    if (!(dp[num][i] & 1))  dp[num][i]++;
                }
            }
        }

        int result = dp[0][0];
        for (int i = 0; i < k; ++i) {
            result = max(*max_element(dp[i].begin(), dp[i].end()), result);
        }
        return result;
    }
};

hope this helps someone. cheers! good luck.