2024 April 13 Problems

78 views
Skip to first unread message

daryl...@gmail.com

unread,
Apr 13, 2024, 12:46:48 PMApr 13
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.



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.

Andriy T

unread,
Apr 13, 2024, 1:42:12 PMApr 13
to leetcode-meetup

T: O(n*lg(n)) S: O(1)

public int minimumBoxes(int[] apple, int[] capacity) {
  int totalApples = 0;
  for (int a = 0;a<apple.length;a++) {
     totalApples += apple[a];
  }
  Arrays.sort(capacity);
  int boxCount = 0;
  int c = capacity.length - 1;
  while (totalApples > 0) {
      totalApples -= capacity[c];
      c--;
      boxCount++;
  }
  return boxCount;
}

Akash Agrawal

unread,
Apr 13, 2024, 1:58:36 PMApr 13
to leetcode-meetup
  T: O(n) S: O(n)

func getSmallestString(s string, k int) string {
newString := []byte{}
var idx int
for idx = 0 ; idx < len(s) && k > 0; idx++ {
result := int(s[idx]-'a')
if result == 0 {
newString = append(newString, s[idx])
continue
}
if result >= 13 { // accommodate for cyclic
result = result*-1 + 26
}
if result <= k {
newString = append(newString, 'a')
k = k-result
} else {
newString = append(newString, s[idx]-byte(k))
k = 0
}
}
return string(newString)+s[idx:]
}

daryl...@gmail.com

unread,
Apr 13, 2024, 2:16:36 PMApr 13
to leetcode-meetup

Basic approach is a greedy solution: take s and go left to right, shifting to either 'a' or whatever character is closest to 'a' if we don't have enough k remaining. We then subtract the amount of distance we shifted the letter from k and then move onto to the next character. The main tricky part is dealing with the cyclic distance, so we have to consider if it would be shorter to wrap around going 'z' -> 'a'. This results in the somewhat clunky code that is using modulus 26 for the wrap around.

O(n) time
O(1) additional space besides the result string

class Solution:
def getSmallestString(self, s: str, k: int) -> str:
res = ""
val = string.ascii_lowercase
def dist(s1, s2):
return min(ord(s1) - ord(s2), (ord(s2) - ord(s1)) % 26)
for letter in s:
diff = min(k, dist(letter, 'a'))
k -= diff
res += val[min(ord(letter) - ord('a') - diff, (ord(letter) - ord('a') + diff) % 26)]
return res

On Saturday, April 13, 2024 at 9:46:48 AM UTC-7 daryl...@gmail.com wrote:

Andriy T

unread,
Apr 13, 2024, 2:29:56 PMApr 13
to leetcode-meetup

I calculate the distance to an if it is possible, make it 'a' if not, make it lexicography smallest 
Time O(n) S: O(1)
class Solution {
    public String getSmallestString(String s, int k) {
        int z = (int)'z';
        int a = (int)'a';

        String res = "";
        for (int i = 0; i<s.length();i++) {
            char ch = s.charAt(i);
            int distToA = Math.min((z - ch + 1),(ch - a));
            if (distToA == (z - ch + 1) && k >= distToA) {
                res += 'a';
                k -= distToA;
            }
            else if (k > 0) {
                res += (char)(((int)ch) - Math.min(distToA, k));
                k-=distToA;
            }
            else {
                res += ch;
            }
        } //for
        return res;
    }
}

Flocela Maldonado

unread,
Apr 13, 2024, 2:30:40 PMApr 13
to leetcode-meetup
3106 Lexicographically Smallest String After Operations With Constraint62.9%Medium
Time O(n), Memory(1)
class Solution {
public:
string getSmallestString(string s, int k) {
int a = 97;
vector<char> v(52);
for(int ii=0; ii<26; ++ii)
{
v[ii] = (char)(a + ii);
v[ii+26] = (char)(a + ii);
}
for(int ii=0; ii<s.size(); ++ii)
{
if(k <= 0)
{
break;
}
int cur = s[ii] - 97;
int ltDiff = min(k, cur);
int lt = cur - ltDiff;
int rtDiff = min(k, (26-cur));
int rt = cur + rtDiff;
if(v[lt] < v[rt])
{
s[ii] = v[lt];
k -= (ltDiff);
}
else if (v[lt] > v[rt])
{
s[ii] = v[rt];
k -= (rtDiff);
}
else
{
s[ii] = v[rt];
k -= std::min(ltDiff, rtDiff);
}
}
return s;
}
};


On Saturday, April 13, 2024 at 11:16:36 AM UTC-7 daryl...@gmail.com wrote:

Anne-Elise Chung

unread,
Apr 13, 2024, 2:35:46 PMApr 13
to leetcode-meetup
3074 apple redistribution:
```
/**
* @param {number[]} apple
* @param {number[]} capacity
* @return {number}
*/
var minimumBoxes = function(apple, capacity) {
let sum = apple.reduce((partialSum, a) => partialSum + a, 0);
let minBoxCount = 0;
capacity.sort((a,b)=> a-b);

while(sum > 0){
sum -= capacity.pop();
minBoxCount++;
}
return minBoxCount;
}; ```

Algorithm description:
My intuition here was that the sum of the values in the apple array was more helpful than the array itself. After getting the sum, you can find the mind boxes by popping the largest boxes off the array and subtracting them from the sum until you reach 0 or less. Every time we pop a box, we increment 1 to the minimum box count, so that we can return the count once we run out of apples.

Time Complexity:
The reduce call in the first call is O(n) where n is the number of apple packs.
The sort call time complexity is O(mlogm) where m is the number of boxes.
The while loop can iterate up to k times depending on the values k in the apple array.
Overall the worst case time complexity is O(n+mlogm+k).

Space Complexity:
The space complexity is O(1) because we are not creating any new arrays or non-constant data structures to solve this.

Any feedback is welcome!
On Saturday, April 13, 2024 at 9:46:48 AM UTC-7 daryl...@gmail.com wrote:

Priyank Gupta

unread,
Apr 13, 2024, 2:48:06 PMApr 13
to leetcode-meetup
# Time : O(nlogn)
# Space: O(n)
import heapq
class Solution:
def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
totalApples = sum(apple)
heapq._heapify_max(capacity)
totalCapacity = 0
count = 0
for _ in range(len(capacity)):
totalCapacity+= heapq._heappop_max(capacity)
count += 1
if totalCapacity>= totalApples:
return count
return -1

Vivek H

unread,
Apr 14, 2024, 1:02:18 AMApr 14
to leetcod...@googlegroups.com
*************************************************************************************************
*************************************************************************************************
O(n) solution

class Solution {
public:
    string getSmallestString(string s, int k) {

        for (int i = 0; i < s.length(); i++) {

            int distFromStart = min(s[i] - 'a', 26 - (s[i] - 'a'));
            if (distFromStart <= k) {
                s[i] = 'a';
                k = k - distFromStart;
                cout << "k:" << k << endl;

            } else {
                s[i] = s[i] - k;
                k = 0;
                if (k == 0)
                    break;
            }
        }
        return s;
    }
};


--
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/da226161-b870-4195-a772-e40a92ef917dn%40googlegroups.com.

Vivek H

unread,
Apr 14, 2024, 1:28:39 AMApr 14
to leetcod...@googlegroups.com
***************************************************************************
***************************************************************************
O(nlogn) solution

class Solution {
public:
    int minimumBoxes(vector<int>& apple, vector<int>& capacity) {

        int totalApples = 0;
        for (int i = 0; i < apple.size(); i++) {
            totalApples += apple[i];
        }

        int minBoxes = 0;
        sort(capacity.begin(), capacity.end(), greater<int>());

        for (int i = 0; i < capacity.size(); i++) {
            totalApples = totalApples - capacity[i];
            minBoxes++;
            if (totalApples <= 0) {
                break;
            }
        }
        return minBoxes;
    }
};

--
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.

vinay

unread,
Apr 14, 2024, 7:10:56 PMApr 14
to leetcod...@googlegroups.com
Greedily determine if you can go to 'a' with minimum cost, so you can use remaining K to form lexicographically smallest word possible


For each character, check if going to character 'a' would cost less going backwards or forward
Then deduct that cost from 'k'  as you iterate.
If the min cost can be afforded using current 'k' then you're able to go to character 'a', so append that. 
else, go backward positions till k and append the resultant character
time o(n), space o(1)

class Solution {
    public String getSmallestString(String s, int k) {
        StringBuilder sb = new StringBuilder();

        for(char c : s.toCharArray()){
            // The 'z'-c+1 is due to fact that the alphabets are cyclic
            //example:
            //abcdefghijklmnopqrstuvwxyz|abcdefghijklmnopqurstuvwyz

            int forward = 'z' - c +1;
            int backward = c - 'a';

            int minDistance = Math.min(forward, backward);
           
            //if you have more K than minDistance, you can go to 'a'.
            //otherwise you just go k spaces back from current alphabet
            if(k >= minDistance){
                sb.append('a');
                k -= minDistance;
            }else{
                char ch = (char) (c - k);
                sb.append(ch);
                k = 0;
            }

           
        }

        return sb.toString();
    }
}


On Sat, Apr 13, 2024 at 11:16 AM daryl...@gmail.com <daryl...@gmail.com> wrote:
--
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/da226161-b870-4195-a772-e40a92ef917dn%40googlegroups.com.
Reply all
Reply to author
Forward
0 new messages