SDE - Intern

Sort both the arrays and then take two variables, i and j, both initially 0 for array a and array b, respectively. if a[i] > b[j] increment both the pointers and increment the answer; if not, then increment only the i pointer.

I solved it by taking a variable current sum till i and calculating the number of odd subarrays and even subarrays in indices.

I used Kadane's Algorithm to solve this problem.

From the test cases, I built the graph for the problem and noticed that its pattern is similar to the Course Schedule problem. I used indegree and outdegree arrays and applied topological sorting to obtain the correct answer.

I started by thinking about a brute-force recursive solution, where for each character mismatch, I would try all three operations and recursively solve the subproblems. However, I realized this would have exponential time complexity. I defined a DP table dp[i][j] where dp[i][j] represents the minimum edit distance between the first i characters of word1 and the first j characters of word2.

I first thought about generating all possible combinations of k digits from both arrays and then picking the maximum, but this was not efficient. I realized I could use a greedy approach to select the maximum subsequence from each array for every possible split (i from 0 to k), and then merge the two subsequences to form the largest number. For each possible split (i digits from the first array, k-i from the second), I generated the two subsequences and merged them by always picking the larger leading digit.