2024 May 18 Problems

68 views
Skip to first unread message

daryl...@gmail.com

unread,
May 18, 2024, 12:31:01 PMMay 18
to leetcode-meetup
Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.

Please post your solutions to this thread so others can use this as a reference.


1048Longest String Chain61.0%Medium



Please download and import the following iCalendar (.ics) files to your calendar system.
Weekly: https://us04web.zoom.us/meeting/upIqc-6upj8sGt0O2fJXTw2gC4FxRMQ-iqAT/ics?icsToken=98tyKu6uqT8tHNyRthmOR7YAB4-gKO7xiCldjbcNs03jKRhndVHxFbZkKoBSIZXZ

Join Zoom Meeting (Meeting starts at 11:30)
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1

Meeting ID: 767 4768 4609
Passcode: 8wf3Qa

Sridevi A

unread,
May 18, 2024, 12:45:51 PMMay 18
to leetcod...@googlegroups.com
Hi,

I am joining this meetup for the first time.  Is the 11:30 AM meeting today in what time zone?

Thank you,
Sridevi



--
whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/0563838c-53d8-490b-b8cb-483bdca5e610n%40googlegroups.com.

Flocela Maldonado

unread,
May 18, 2024, 1:04:16 PMMay 18
to leetcode-meetup
Sridevi, The zoom meeting is at 11:30 am Pacific Daylight Time. (Same as San Francisco, CA).

-Flo

Sridevi A

unread,
May 18, 2024, 1:06:49 PMMay 18
to leetcod...@googlegroups.com
Hi Flocela,

Thank you so much! Looking forward to it!

Sridevi


To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/5f4667b5-7d87-458e-99cb-28f834b00575n%40googlegroups.com.

Vivek H

unread,
May 18, 2024, 1:08:31 PMMay 18
to leetcod...@googlegroups.com
*******************************************************************
*******************************************************************

TC  = O(n)
SC = O(1)

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

        int i = m-1;
        int j = n-1;
        int end = m+n-1;

        while(i>=0 && j>=0) {
            if(nums1[i] < nums2[j]) {
                nums1[end--] = nums2[j];
                j--;
            } else if(nums1[i] > nums2[j]) {
                //nums1[i] = INT_MIN;
                nums1[end--] = nums1[i];
               
                i--;
            } else {
                nums1[end--] = nums1[i];
                nums1[end--] = nums2[j];
                i--; j--;
            }
        }

        if(j>=0) {
        while(j>=0) {
            nums1[end] = nums2[j];
            end--; j--;
        }
        }
       
    }
};

--

Flocela Maldonado

unread,
May 18, 2024, 1:22:59 PMMay 18
to leetcode-meetup
88Merge Sorted Array49.7%Easy
Time: O(n+m), Memory: O(1)
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { // index for nums1. int mIdx = m-1; // index for nums2. int nIdx = n-1; // move along nums1, from right side to left. for(int ii=nums1.size()-1; ii>=0; --ii) { if(nIdx == -1) { nums1[ii] = nums1[mIdx]; --mIdx; } else if(mIdx == -1) { nums1[ii] = nums2[nIdx]; --nIdx; } else if(nums1[mIdx] > nums2[nIdx]) { nums1[ii] = nums1[mIdx]; --mIdx; } else { nums1[ii] = nums2[nIdx]; --nIdx; } } } };

Flocela Maldonado

unread,
May 18, 2024, 1:27:10 PMMay 18
to leetcode-meetup
1048Longest String Chain61.0%Medium
With Hint 2: Time: O(n^2), Memory: O(n). Where n is the number of words.
class Solution {
public:

// Iterate through tree, where every node is a word. And every node's children are the set of predecessors associated with that word.
int dfsGetHeight(const string& word, unordered_map<string, unordered_set<string>>& setOfPredecessorsPerWord)
{
int maxH = 0;
for(const string& predecessor : setOfPredecessorsPerWord[word])
{
int height = dfsGetHeight(predecessor, setOfPredecessorsPerWord);
maxH = std::max(maxH, height);
}

return maxH + 1;
}

int longestStrChain(vector<string>& words) {

// Group the words by their length.
unordered_map<int, unordered_set<string>> wordsPerLength{};
for(const string& word : words)
{
if(wordsPerLength.find(word.size()) == wordsPerLength.end())
{
wordsPerLength.insert({word.size(), unordered_set<string>{}});
}
wordsPerLength[word.size()].insert(word);
}

// Every unique word has a set of predecessors (could be the empty set).
unordered_map<string, unordered_set<string>> setOfPredecessorsPerWord{};
for(const string& word : words)
{
if(setOfPredecessorsPerWord.find(word) == setOfPredecessorsPerWord.end())
{
setOfPredecessorsPerWord.insert({word, unordered_set<string>{}});
}
}

unordered_set<string> wordIsSeen{};

// Add predecessors to each word's predecessorSet.
for(const string& word : words)
{
// Don't do the same word twice. Already found the predecessors for this word.
if(wordIsSeen.find(word) != wordIsSeen.end())
{
continue;
}
wordIsSeen.insert(word);

// If there are no words with a length of one smaller than the word, then continue to next word.
if(wordsPerLength.find(word.size()-1) == wordsPerLength.end())
{
continue;
}

// Check every word with the correct length (that's word.size()-1) to see if it's a predecessor.
for(string shortWord : wordsPerLength[word.size()-1])
{
// short word's index
int s_ii = 0;

// w_ii is the word's index
int w_ii = 0;

while(w_ii < word.size() && s_ii < shortWord.size())
{
// if the letter's don't match, skip this letter in word.
if(word[w_ii] != shortWord[s_ii])
{
++w_ii;
}
else
{
++s_ii;
++w_ii;
}

// if already skipped more than 1 letter, then it's not a predecessor, break.
if ( (w_ii-s_ii) > 1)
{
break;
}
}

// It's a predecessor if zero or more letters were skipped.
if (w_ii-s_ii <= 1)
{
setOfPredecessorsPerWord[word].insert(shortWord);
}
}
}

vector<int> wordLengths{};
for(auto& lengthAndWords : wordsPerLength)
{
wordLengths.push_back(lengthAndWords.first);
}

sort(wordLengths.begin(), wordLengths.end(), [](const int& a, const int& b){ return b < a;});

// length of longest word chain
int maxWC = 0;

// Go through each word, but do the long words first (using sorted wordLengths).
for(int length : wordLengths)
{
// if the length of these words are smaller than the longest word chain, then there's no chance that the word will make a longer word chain than maxWC.
// The longest word chain a word can make is it's length.
if(length < maxWC)
{
break;
}
for(auto& word : wordsPerLength[length])
{
int height = dfsGetHeight(word, setOfPredecessorsPerWord);
maxWC = std::max(maxWC, height);
}
}

return maxWC;
}
};

Allen S.

unread,
May 18, 2024, 2:06:12 PMMay 18
to leetcode-meetup
GoLang Solution for 
```
func merge(nums1 []int, m int, nums2 []int, n int)  {
    // start from end of nums1
    for i := m + n - 1; i >= 0 && n > 0 ; i-- {
        if m == 0 || nums1[m-1] < nums2[n-1] {
            nums1[i] = nums2[n-1]
            n--
        } else {
            nums1[i] = nums1[m-1]
            m--
        }
    }
}
```

Allen S.

unread,
May 18, 2024, 2:43:47 PMMay 18
to leetcode-meetup
func longestStrChain(words []string) int {
// start from longer words (successors), go to look for shorter (predecessors)
// to do that removing each letter, one by ne
// build a tree
// count levels
}

Allen S.

unread,
May 18, 2024, 3:16:54 PMMay 18
to leetcode-meetup
Guys, it's very nice meeting you. Thank you for the meeting. Great skill level. One can learn a lot. Do you mind sharing your linkedin pages? So we can connect and get introduced to each other's backgrounds.

Allen S.

unread,
May 18, 2024, 3:19:46 PMMay 18
to leetcode-meetup
Here is my linkedin: https://www.linkedin.com/in/allen-eng/
Feel free to connect. :)

vinay

unread,
May 19, 2024, 1:08:12 PMMay 19
to leetcod...@googlegroups.com
Start with the ends of both arrays and have a pointer to fill arr1 from the end.

Element with greater value of the two gets elected to be filled at the end of arr1, because of the fact that both arrays are sorted.

Once you detect out of bounds for either array, start filling the arr1 with remaining elements

time O(m+n)
space O(1)

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
            int pointer = nums1.length-1;
            //adjust the bounds
            m--;
            n--;
           
            while(m >= 0 && n >= 0){
                if(nums1[m] > nums2[n]){
                    nums1[pointer] = nums1[m];
                    m--;
                }else{
                    nums1[pointer] = nums2[n];
                    n--;
                }
                pointer--;
            }

             while(m >= 0){
                nums1[pointer] = nums1[m];
                m--;
                pointer--;
             }
             
             while(n >= 0){
                nums1[pointer] = nums2[n];
                n--;
                pointer--;
             }

    }
}



To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/29c926bf-d1c1-4ac9-ac3e-437cb6c0b692n%40googlegroups.com.
Reply all
Reply to author
Forward
0 new messages