2024 April 20 Problems

[daryl...@gmail.com]

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.

219Contains Duplicate II45.0%Easy

215Kth Largest Element in an Array66.8%Medium

220Contains Duplicate III22.7%Hard

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
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1

Meeting ID: 767 4768 4609
Passcode: 8wf3Qa

Reminder that we have the monthly meet up for coffee afterwards for anyone attending live.

[Vivek H]

*****************************************************************

215Kth Largest Element in an Array66.8%Medium

*****************************************************************

class Solution {

public:

    struct comp {

        bool operator()(int a, int b) {

            return a > b;

        }

    };

    int findKthLargest(vector<int>& nums, int k) {

        priority_queue<int, vector<int>, comp> PQ;

        for(int i=0; i<k; i++) {

            PQ.push(nums[i]);

        }

        for(int i=k; i<nums.size(); i++) {

            if(PQ.top() < nums[i]) {

                PQ.pop(); PQ.push(nums[i]);

            }

        }

        return PQ.top();

       

    }

};

--
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/0f8e3718-c856-4bba-aaef-503908d36addn%40googlegroups.com.

[Vivek H]

***************************************************************

219Contains Duplicate II45.0%Easy

***************************************************************

class Solution {

public:

    bool containsNearbyDuplicate(vector<int>& nums, int k) {

       

       

        map<int, vector<int>> M;

        for(int i=0; i<nums.size(); i++) {

            M[nums[i]].push_back(i);

        }

        for(auto &a : M) {

            vector<int> V = a.second;

            if(V.size() <=1)

                continue;

            for(int i=1; i<V.size(); i++) {

                if(V[i]-V[i-1] <= k)

                    return true;

            }

        }

        return false;

    }

};

On Sat, Apr 20, 2024 at 9:44 AM daryl...@gmail.com <daryl...@gmail.com> wrote:

--

[Flocela Maldonado]

219Contains Duplicate II45.0%Easy
Time O(n) Memory O(k)

class Solution {

public:

bool containsNearbyDuplicate(vector<int>& nums, int k) {

//mapOfCountPerValue contains the values in the window from [lt, rt]

unordered_map<int, int> mapOfCountPerValue{};

int lt = 0;

int rt = 0;

mapOfCountPerValue.insert({nums[lt], 1});

for(int ii=0; ii<nums.size(); ++ii)

{

int num = nums[ii];

// update the window of values (move lt to the right) and update mapOfCountPerValue.

// remove value nums[lt], then increase lt.

for(; lt<ii; ++lt)

{

--mapOfCountPerValue[nums[lt]];

}

// update the window of values (move rt to the right) and update mapOfCountPerValue.

// add values nums[rt+1], then increase rt.

for(; rt<(ii+k); ++rt)

{

if(rt+1 >= nums.size())

{

break;

}

++mapOfCountPerValue[nums[rt+1]];

}

// Are there two nums in mapOfCountPerValue (one of the nums is the num at ii, that's

// why we need 2).

if(mapOfCountPerValue.find(num) != mapOfCountPerValue.end() &&

mapOfCountPerValue[num] >= 2)

{

return true;

}

}

return false;

}

};

[Flocela Maldonado]

220Contains Duplicate III22.7%Hard
Using 2nd hint: Time: O(n + n log(k)), Memory: O(n + k). Where n is the size of nums and k is the indexDiff

class Solution {

public:

bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {

int n = nums.size();

// Make a vector of pairs. Each pair is the value in nums and its index.

vector<pair<int, int>> numAndIndexVector(n);

for(int ii=0; ii<n; ++ii)

{

numAndIndexVector[ii] = pair<int, int>{nums[ii], ii};

}

// Evaluate a chunk of numAndIndexVector to see if any of its values and their indices are within the

// valueDiff and indexDiff criteria.

int chunk = (2 * (indexDiff+1));

// sortedArray will be a vector (of size chunk) of sorted pairs.

vector<pair<int, int>> sortedArray(chunk);

// At each iteration. Take a chunk of values from numAndIndexVector put them into sortedArray and sort them.

// Then test each pair against the adjacent pair. Check if this pair's index compared with the adjacent pair's index

// are within indexDiff and similarly that the values are within valueDiff.

// If adjacent pairs do not have indexes within indexDiff, then move the to the next adjacent pair, compare this test pair

//with the next adjacent pair.

// All pairs are tested against all pairs in this chunk.

// Only increase ii by chunk/2. The pairs that were originally at the end of the chunk

// in numAndIndexVector still need to be tested against the pairs in the next chunk. So include the last half of this chunk in

// the next chunk. So the beginning of the chunk in numAndIndexVector was tested in the last iteration

// against pairs in the last chunk and is now tested against pairs in this chunk.

for(int ii=0; ii<n; ii+=(chunk/2))

{

// Populating sortedArray. If there's not enough pairs, then only go to end of the numAndIndexVector.

// The last sortedArray may not have a full chunk of pairs.

if (ii + chunk < n)

{

copy(numAndIndexVector.begin()+ii, numAndIndexVector.begin()+ii+chunk, sortedArray.begin());

sort(sortedArray.begin(), sortedArray.end());

}

else

{

sortedArray = vector<pair<int, int>>(n - ii);

copy(numAndIndexVector.begin()+ii, numAndIndexVector.end(), sortedArray.begin());

sort(sortedArray.begin(), sortedArray.end());

}

// Testing a pair means checking to see if there is a value in the chunk within valueDiff. The pairs are

// sorted by value. So check adjacent values. But it may be the case that adjacent values in sortedArray are

// not within the indexDiff. In that case move out from the testing pair until a pair is found that is

// within indexDiff and then see if it is within the valueDiff. If a pair is found that is within indexDiff and

// not within valueDiff then going out farther will not produce a pair that is within valueDiff because

// pairs are sorted by value.

for(int jj=0; jj<sortedArray.size(); ++jj)

{

int kk = jj+1;

while((kk < sortedArray.size()) && (abs(sortedArray[jj].second - sortedArray[kk].second) > indexDiff))

{

++kk;

}

if((kk <sortedArray.size()) && ((sortedArray[kk].first - sortedArray[jj].first) <= valueDiff))

{

return true;

}

}

}

return false;

}

};