Skip to content

Latest commit

 

History

History
237 lines (175 loc) · 7.5 KB

_1940. Longest Common Subsequence Between Sorted Arrays.md

File metadata and controls

237 lines (175 loc) · 7.5 KB

1940. Longest Common Subsequence Between Sorted Arrays

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

First completed : June 01, 2024

Last updated : July 01, 2024

Related Topics : Array, Hash Table, Counting

Acceptance Rate : 81.33 %

Solutions

Python

m1940 Iterative Removed TryExcept.py

# weekly premium question

''' Notes
    I adjusted this from the original first success attempt to avoid the try-except block since
    I thought maybe that could cause overhead and while it did "improve," it's changed from a 
    consistently above-average runtime (bad) to a inconsistently high-low ranging runtime. On average,
    it *is* better... the first run I tried with it resulted in a top 95% lol. But idk. It's interesting.
'''


class Solution:
    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:
        output = []

        pointers = [0] * len(arrays)
        maxCurrent = arrays[0][pointers[0]]
        pointerOfPointer = 1

        counter = 1
        while pointers[pointerOfPointer] < len(arrays[pointerOfPointer]) :
            if arrays[pointerOfPointer][pointers[pointerOfPointer]] < maxCurrent :
                pointers[pointerOfPointer] += 1
                continue

            if arrays[pointerOfPointer][pointers[pointerOfPointer]] > maxCurrent :
                maxCurrent = arrays[pointerOfPointer][pointers[pointerOfPointer]]
                counter = 1
                pointerOfPointer = (pointerOfPointer + 1) % len(pointers)
                continue
            
            counter += 1
            pointers[pointerOfPointer] += 1
            pointerOfPointer = (pointerOfPointer + 1) % len(pointers)
            
            if counter == len(pointers) :
                output.append(maxCurrent)
                counter = 0

        return output

m1940 Iterative TryExcept.py

# weekly premium question

# Rank: 3

# Method iterates through O(m*n) where m=len(arrays) and n=max(len(array[i]))


class Solution:
    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:
        output = []

        pointers = [0] * len(arrays)
        maxCurrent = arrays[0][pointers[0]]
        pointerOfPointer = 1

        counter = 1
        try :
            while True :
                if arrays[pointerOfPointer][pointers[pointerOfPointer]] < maxCurrent :
                    pointers[pointerOfPointer] += 1
                    continue

                if arrays[pointerOfPointer][pointers[pointerOfPointer]] > maxCurrent :
                    maxCurrent = arrays[pointerOfPointer][pointers[pointerOfPointer]]
                    counter = 1
                    pointerOfPointer = (pointerOfPointer + 1) % len(pointers)
                    continue

                if counter == len(pointers) :
                    output.append(maxCurrent)
                    pointers = [i + 1 for i in pointers]
                    counter = 0
                    continue
                
                counter += 1
                pointerOfPointer = (pointerOfPointer + 1) % len(pointers)
        except IndexError :
            return output

m1940 Weekly Premium subset method.py

# weekly premium question
# Rank: 1

# Notably faster than the iterative approach, perhaps due to the O(1) set usage?
# I think this is O(n*m) where n is the total number of terms in all arrays summed
# and m is the max number of terms in a single subarray
# --> cost is due to the intersection being O(m) max case and done n-1 times

class Solution:
    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:
        outputSet = set(arrays[0])

        for arrayCase in arrays :
            outputSet &= set(arrayCase)

        return sorted(list(outputSet))

m1940 counter.py

# weekly premium question

# Rank: 2

# Counts occurances of each number
# Since all values are STRICTLY increasing, repeats aren't present
# 2'd fastest it seems behind the subset method

class Solution:
    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:
        counter = {}

        for subArr in arrays :
            for i in subArr :
                counter[i] = counter.get(i, 0) + 1
        
        return [x for x in counter.keys() if counter.get(x, 0) == len(arrays)]

Java

m1940 Iterative.java

// weekly premium question

// Interesting how for java, this solution with iterating is MUCH faster than the
// HashMap Counter method. But with Python, both the Counter and Set methods are
// MUCH faster than this iterative approach. I wonder why....

class Solution {
    public List<Integer> longestCommonSubsequence(int[][] arrays) {
        ArrayList<Integer> output = new ArrayList<>();

        int[] pointers = new int[arrays.length];
        int pointerForPointers = 0;

        int counter = 0;
        int currentMaxValue = Integer.MIN_VALUE;

        while (arrays[pointerForPointers].length > pointers[pointerForPointers]) {
            if (arrays[pointerForPointers][pointers[pointerForPointers]] < currentMaxValue) {
                pointers[pointerForPointers] += 1;
                continue;
            }

            // if (arrays[pointerForPointers][pointers[pointerForPointers]] > currentMaxValue) {
            currentMaxValue = arrays[pointerForPointers][pointers[pointerForPointers]];
            pointerForPointers = (pointerForPointers + 1) % pointers.length;
            counter = 1;
            continue;
            // }

            counter += 1;
            pointers[pointerForPointers] += 1;
            pointerForPointers = (pointerForPointers + 1) % pointers.length;

            if (counter == pointers.length) {
                output.add(currentMaxValue);
                currentMaxValue = arrays[pointerForPointers][pointers[pointerForPointers]];
                counter = 0;
            }
        }

        return output;

    }
}

m1940 counter.java

// weekly premium question

class Solution {
    public List<Integer> longestCommonSubsequence(int[][] arrays) {
        HashMap<Integer, Integer> counter = new HashMap<>();

        for (int[] subArr: arrays){
            for (int i: subArr) {
                counter.put(i, counter.getOrDefault(i, 0) + 1);
            }
        }

        ArrayList<Integer> output = new ArrayList<>();
        
        for (int i: counter.keySet()) {
            if (counter.getOrDefault(i, 0) == arrays.length) {
                output.add(i);
            }
        }
        Collections.sort(output);

        return output;
    }
}