2025 November 15 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.

Medium and hard problems are carried over.

912. Sort an Array Medium 56.1%

1733. Minimum Number of People to Teach Medium 67.8%

1735. Count Ways to Make Array With Product Hard 53.8%

We're going to try to use the same Google meet link as last time: https://meet.google.com/xnn-kifj-jnx?pli=1 

If it doesn't work I'll post the usual Zoom meeting

[FloM]

Daryl,

Didn't Anuj present this hard problem last week?

-Flo

[daryl...@gmail.com]

I missed that when reviewing the problems this week. I was looking for a bucket sort problem but haven't found one, so I'm adding the following hard problem if people want:

483. Smallest Good Base Hard 44.7% 

[Anuj Patnaik]

class Solution:

def sortArray(self, nums: List[int]) -> List[int]:

if len(nums) == 1:

return nums

mid = len(nums) // 2

left_merge_arr = nums[0: mid]

right_merge_arr = nums[mid:]

left_sort = Solution.sortArray(self,left_merge_arr)

right_sort = Solution.sortArray(self, right_merge_arr)

return Solution.merge(left_sort, right_sort)

def merge(left_arr, right_arr):

merged_arr = []

i = 0

j = 0

while i < len(left_arr) and j < len(right_arr):

if left_arr[i] < right_arr[j]:

merged_arr.append(left_arr[i])

i = i + 1

elif left_arr[i] > right_arr[j]:

merged_arr.append(right_arr[j])

j = j + 1

else:

merged_arr.append(right_arr[j])

merged_arr.append(left_arr[i])

i += 1

j += 1

while i < len(left_arr):

merged_arr.append(left_arr[i])

i = i + 1

while j < len(right_arr):

merged_arr.append(right_arr[j])

j = j + 1

return merged_arr

[Gowrima Jayaramu]

class Solution:

def partition(self, nums, start, end):

pivot = end

i = start-1

for j in range(start, end):

if nums[j] <= nums[pivot]:

i += 1

nums[i], nums[j] = nums[j], nums[i]

nums[i+1], nums[end] = nums[end], nums[i+1]

return i+1

def quicksort(self, nums, start, end):

if start<end:

q = self.partition(nums, start, end)

self.quicksort(nums, start, q-1)

self.quicksort(nums, q+1, end)

return nums

def sortArray(self, nums: List[int]) -> List[int]:

return self.quicksort(nums, 0, len(nums)-1)

# Time: O(nlogn) average case, O(n^2) worst case

# Space: O(logn) average case, O(n) worst case

[Anuj Patnaik]

class Solution:

def smallestGoodBase(self, n: str) -> str:

n = int(n)

max_base = int(math.log2(n+1))

for b in range(max_base, 1, -1):

left = 2

right = int(n**(1/(b-1))) + 1

while left <= right:

k = left + (right - left)//2

total = ((k ** b) - 1)// (k - 1)

if total == n:

return str(k)

elif total < n:

left = k + 1

else:

right = k - 1

return str(n-1)

[Bhupathi Kakarlapudi]

Quick sort solution with time complexity O(nlogn) and space complexity O(n):

class Solution:

def sortArray(self, nums: List[int]) -> List[int]:

if len(nums) <= 1:

return nums # a list with 0 or 1 element

low = 0

high = len(nums)-1

pivot = nums[randint(low, high)]

# create sub-arrays for elements less than, equal to, greater than the pivot

left = [x for x in nums if x < pivot]

middle = [x for x in nums if x == pivot]

right = [x for x in nums if x > pivot]

# recursively sort the left and right sub-arrays and combine them with middle

return self.sortArray(left) + middle + self.sortArray(right)

--
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 visit https://groups.google.com/d/msgid/leetcode-meetup/e8effd63-a1b6-4d17-87a9-de1dc3cd5f5bn%40googlegroups.com.

[FloM]

1733. Minimum Number of People to Teach Medium 67.8%

Mem: O(m^2 + m), Time: O(m*n + m^2) where m= number of users, n=number of languages

class Solution {

public:

// Returns true if user u and user v have a matching language.

// u and v are zero-based indexed users.

// languageSets[i] contains user i's languages.

bool areSpeaking(int u, int v, vector<vector<uint64_t>>& languageSets)

{

for(int ii=0; ii<languageSets[0].size(); ++ii)

{

if ( (languageSets[u][ii] & languageSets[v][ii]) != 0)

{

return true;

}

}

return false;

}

int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {

int numUsers = languages.size();

int langBin = 50; // number of languages held in each number of languageSets[userNum].

int k = (n/langBin) +1;

// languageSets[i] contains user i's languages.

// Say there are 100 languages, then languagesSets[i] will be a vector of size 2.

// The first 50 languages will be kept in languageSets[i][0], the second 50 langugages

// will be kept in languagesSets[i][1].

// The numbers at languagesSets[i][x] record which languages are spoken.

// If user_i speaks languages 25 and 62, then languageSets[i][0] will be 2^25, and

// languageSets[i][1] will be 2^12. (Note 62%50 = 12.)

// The binary one in the number represents the language.

vector<vector<uint64_t>> languageSets(numUsers, vector<uint64_t>(k, 0));

// Populate languageSets

for(int user=0; user<numUsers; ++user)

{

for(int lang : languages[user])

{

int languageSet = lang / langBin;

uint64_t langIdx = lang % langBin;

uint64_t one = 1;

uint64_t shift = (one << langIdx);

languageSets[user][languageSet] = ((languageSets[user][languageSet]) | shift);

}

}

// nonSpeakingFriends keeps the set of non-speaking friends for each user.

// Not all nonSpeakingFriends are included. Only non-speaking freinds who are

// larger than user. u > v. This way, only one edge is in nonSpeakingFriends for

// each u-v friendship.

vector<unordered_set<int>> nonSpeakingFriends(numUsers, unordered_set<int>{});

for(int friendshipIdx=0; friendshipIdx<friendships.size(); ++friendshipIdx)

{

int u = (friendships[friendshipIdx][0] <= friendships[friendshipIdx][1]) ?

(friendships[friendshipIdx][0]) :

(friendships[friendshipIdx][1]);

int v = (friendships[friendshipIdx][0] <= friendships[friendshipIdx][1]) ?

(friendships[friendshipIdx][1]) :

(friendships[friendshipIdx][u]);

// Make friendship users zero-based indexed.

--u;

--v;

if (!areSpeaking(u, v, languageSets))

{

nonSpeakingFriends[u].insert(v);

}

}

// Answer. If a user has non-speaking friends, then the only way that user

// will ever talk to them is if they both know lang.

// So try each lang (only allowed to learn one language at a time).

int minUsersTaught = 1000;

for(int lang=1; lang<n+1; ++lang)

{

unordered_set<int> newSpeakers{};

int languageSet = lang / langBin;

uint64_t langIdx = lang % langBin;

for(int user=0; user<numUsers; ++user)

{

uint64_t one = 1;

uint64_t shift = (one << langIdx);

// if user doesn't know lang and user has non-speaking friends,

// then insert into newSpeakers_set.

if ( ((languageSets[user][languageSet] & shift) == 0) &&

(!nonSpeakingFriends[user].empty()))

{

newSpeakers.insert(user);

}

// Insert all non-speaking friends, who don't know lang, into newSpeakers as well.

for(int nonSpeakingFriend : nonSpeakingFriends[user])

{

if ( (languageSets[nonSpeakingFriend][languageSet] & shift) == 0)

{

newSpeakers.insert(nonSpeakingFriend);

}

}

}

// Compare number of new speakers for this lang to all other langs.

minUsersTaught = std::min(minUsersTaught, static_cast<int>(newSpeakers.size()));

}

return minUsersTaught;

}

};