2024 October 26 Problems

daryl...@gmail.com

unread,

Oct 26, 2024, 12:33:23 PM10/26/24

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.

1. Two Sum Easy 54.1%

2043. Simple Bank System Medium 63.7%

2564. Substring XOR Queries Medium 33.7%

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

Arjun Malhotra

unread,

Oct 26, 2024, 1:19:32 PM10/26/24

to leetcode-meetup

func twoSum(nums []int, target int) []int {
    indexMap := make(map[int]int)
    
    for i:=0;i<len(nums);i++ {
        if _, ok := indexMap[target-nums[i]];ok {
            return []int{indexMap[target-nums[i]], i}
        }
        indexMap[nums[i]]=i
    }

    return []int{-1,-1}
}

Flocela Maldonado

unread,

Oct 26, 2024, 1:21:33 PM10/26/24

to leetcode-meetup

1. Two Sum Easy 54.1%

Time: O(n). Memory: O(n)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, vector<int>> vectorOfIndicesPerNum{};

        for(int ii=0; ii<nums.size(); ++ii)
        {
            int cur = nums[ii];
            if(vectorOfIndicesPerNum.find(cur) == vectorOfIndicesPerNum.end())
            {
                vectorOfIndicesPerNum.insert({cur, vector<int>{}});
            }
            vectorOfIndicesPerNum[cur].push_back(ii);
        }

        for(int ii=0; ii<nums.size(); ++ii)
        {
            int cur = nums[ii];
            int diff = target - cur;
            if(vectorOfIndicesPerNum.find(diff) != vectorOfIndicesPerNum.end())
            {
                if (diff == cur)
                {
                    if(vectorOfIndicesPerNum[cur].size() == 2)
                    {
                        return vectorOfIndicesPerNum[cur];
                    }
                }
                else
                {
                    int diffIndex = vectorOfIndicesPerNum[diff][0];
                    vector<int> ans{ii, diffIndex};
                    return ans;
                }
            }
        }

        return vector<int>{};
    }
};

Anushree Yadav

unread,

Oct 26, 2024, 1:22:58 PM10/26/24

to leetcode-meetup

Time Complexity - O(n^2)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> ret;
        int size = nums.size();
        for (int i = 0; i < size-1; i++)
        {
            for (int j = i+1; j<size; j++)
            {
                if (nums[i] + nums[j] == target)
                {
                    ret.push_back(i);
                    ret.push_back(j);
                    return ret;
                }
            }
        }
        return ret={-1,-1};
    }
};

On Saturday, October 26, 2024 at 10:19:32 AM UTC-7 arjun1m...@gmail.com wrote:

rajat aggarwal

unread,

Oct 26, 2024, 1:27:50 PM10/26/24

to leetcod...@googlegroups.com

1. Two Sum Easy 54.1%

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map= new HashMap<>();
        int result[]= new int[2];

        for(int i=0; i< nums.length; i++){
            if(map.containsKey(target-nums[i]) == true){
                result[0]=i;
                result[1]= map.get(target-nums[i]);
                break;
            } else {
                map.put(nums[i], i);
            }
        }
        return result;
    }
}

--
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/ca1fdd44-13f3-4e68-b513-023359add9cen%40googlegroups.com.

Message has been deleted

Carrie Lastname

unread,

Oct 26, 2024, 1:41:57 PM10/26/24

to leetcode-meetup

Two sum

Time and space complexity: O(n)

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        c = {}
        for i, n in enumerate(nums):
            if target-n in c:
                return [i, c[target-n]]
            c[n] = i

Kevin Burleigh

unread,

Oct 26, 2024, 1:55:24 PM10/26/24

to leetcode-meetup

1. Two Sum Easy 54.1%

time: O(N)

space: O(N)

class Solution:

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

        idx_by_val = {}
        for num_idx,num in enumerate(nums):
            partner = target - num
            if partner in idx_by_val:
                return [num_idx, idx_by_val[partner]]
            idx_by_val[num] = num_idx
        

2043. Simple Bank System Medium 63.7%

time: O(transactions)

space: O(accounts)

class Bank:

    def __init__(self, balance: List[int]):
        self.balances     = balance
        self.num_accounts = len(self.balances)
    
    def _account_is_valid (self, account):
        return 1 <= account <= self.num_accounts

    def transfer(self, account1: int, account2: int, money: int) -> bool:
        if not self._account_is_valid(account1) or not self._account_is_valid(account2):
            return False
            
        if self.withdraw(account1, money):
            return self.deposit(account2, money)
        else:
            return False

    def deposit(self, account: int, money: int) -> bool:
        if not self._account_is_valid(account):
            return False
        account_idx = account - 1
        self.balances[account_idx] += money
        return True                

    def withdraw(self, account: int, money: int) -> bool:
        if not self._account_is_valid(account):
            return False

        account_idx = account - 1
        if money <= self.balances[account_idx]:
            self.balances[account_idx] -= money
            return True
        else:
            return False

2564. Substring XOR Queries Medium 33.7%

time: O(len(s) + queries)

space: O(len(s))

class Solution:
    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:
        ## preprocess s to avoid TLEs due to repeated string searches
        idxs_by_substr = {}
        for substr_len in range(1,31):
            for lo_idx in range(len(s)):
                hi_idx = lo_idx + substr_len-1
                if hi_idx > len(s):
                    next
                substr= s[lo_idx:hi_idx+1]
                if substr not in idxs_by_substr:
                    idxs_by_substr[substr] = [lo_idx, hi_idx]

        results = []
        for query_idx,query in enumerate(queries):
            target_value = query[0] ^ query[1] ## math FTW!
            target_str = "{0:b}".format(target_value) ## dirty trick :)
            if target_str in idxs_by_substr:
                results.append(idxs_by_substr[target_str])
            else:
                results.append([-1,-1])
            
        return results

Arjun Malhotra

unread,

Oct 26, 2024, 1:59:28 PM10/26/24

to leetcode-meetup

type Bank struct {
    balance []int64
}

func Constructor(balance []int64) Bank {
    return Bank{
        balance: balance,
    }
}

func (this *Bank) isValid(account int) bool {
    if account <= 0 || account > len(this.balance) {
        return false
    }
    return true
}

func (this *Bank) Transfer(account1 int, account2 int, money int64) bool {
    if !this.isValid(account1) {
        return false
    }

    if !this.isValid(account2) {
        return false
    }

    if this.balance[account1-1] < money {
        return false
    }

    this.balance[account1-1] = this.balance[account1-1] - money
    this.balance[account2-1] = this.balance[account2-1] + money

    return true
}

func (this *Bank) Deposit(account int, money int64) bool {
    if !this.isValid(account) {
        return false
    }

    this.balance[account-1] = this.balance[account-1] + money
    return true
}

func (this *Bank) Withdraw(account int, money int64) bool {
    if !this.isValid(account) {
        return false
    }

    if this.balance[account-1] < money {
        return false
    }

    this.balance[account-1] = this.balance[account-1] - money
    return true
}

Carrie Lastname

unread,

Oct 26, 2024, 2:03:23 PM10/26/24

to leetcode-meetup

Simple Bank System

class Bank:

    def __init__(self, balance: List[int]):

        self.balances = [0] + balance

    def in_bound(self, account):
        return account < len(self.balances) and account > 0

    def transfer(self, account1: int, account2: int, money: int) -> bool:

        if not self.in_bound(account1) or not self.in_bound(account2):
            return False
        if money > self.balances[account1]:
            return False
        self.balances[account2] += money
        self.balances[account1] -= money
        return True

    def deposit(self, account: int, money: int) -> bool:

        if not self.in_bound(account):
            return False
        self.balances[account] += money

        return True

    def withdraw(self, account: int, money: int) -> bool:

        if not self.in_bound(account):
            return False
        if money > self.balances[account]:
            return False
        self.balances[account] -= money
        return True
        

On Saturday, October 26, 2024 at 9:33:23 AM UTC-7 daryl...@gmail.com wrote:

rajat aggarwal

unread,

Oct 26, 2024, 2:06:41 PM10/26/24

to leetcod...@googlegroups.com

2043. Simple Bank System Medium 63.7%

class Bank {

    long accounts[];
    int startAcNum;
    int endAcNum;

    public Bank(long[] balance) {
        accounts = new long[balance.length];
        accounts = balance;
        startAcNum = 1;
        endAcNum = balance.length;
        // System.out.println(Arrays.toString(accounts));
        // System.out.println(accounts.length);
    }
    
    public boolean transfer(int account1, int account2, long money) {

        if(!isValidAc(account1))
        {
            return false;
        }
        if(!isValidAc(account2))
        {
            return false;
        }

        if( accounts[account1-1] >= money){
            accounts[account1-1] -= money;
            accounts[account2-1] += money;
            return true;
        }

        return false;
    }
    
    public boolean deposit(int account, long money) {
        if(!isValidAc(account))
        {
            return false;
        }       

        accounts[account-1] += money;

        return true;        
    }
    
    public boolean withdraw(int account, long money) {
        if(!isValidAc(account))
        {
            return false;
        }
        
        if( accounts[account-1] >= money){
            accounts[account-1] -= money;            
            return true;
        }
        
        return false;        
    }

    private boolean isValidAc(int account){
        if(account >= startAcNum && account <= endAcNum )
        {
            return true;
        }
        
        return false;
    }

}

On Sat, Oct 26, 2024 at 10:19 AM Arjun Malhotra <arjun1m...@gmail.com> wrote:

--

Flocela Maldonado

unread,

Oct 26, 2024, 2:22:29 PM10/26/24

to leetcode-meetup

2043. Simple Bank System Medium 63.7%

class Bank {
public:
    Bank(vector<long long>& balance) {
        _balance = balance;
    }

    bool validAccount(int x)
    {
        return ( (x > 0) && (x <= _balance.size()) );
    }
    
    bool transfer(int account1, int account2, long long money) {
        if ( !(validAccount(account1) && validAccount(account2)) )
        { 
            return false;
        }

        int acc1Idx = account1 - 1;
        int acc2Idx = account2 - 1;
        if(_balance[acc1Idx] < money)
        {
            return false;
        }
        _balance[acc1Idx] -= money;
        _balance[acc2Idx] += money;
        return true;
    }
    
    bool deposit(int account, long long money) {
        if(!validAccount(account))
        {
            return false;
        }

        int accIdx = account - 1;
        _balance[accIdx] += money;
        return true;
    }
    
    bool withdraw(int account, long long money) {
        if(!validAccount(account))
        {
            return false;
        }
        
        int accIdx = account - 1;
        if(_balance[accIdx] < money)
        {
            return false;
        }
        _balance[accIdx] -= money;
        return true;
    }

    vector<long long> _balance{};
};

Sourabh Majumdar

unread,

Oct 26, 2024, 2:29:12 PM10/26/24

to leetcode-meetup

1. TwoSum

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        

        std::unordered_map<int, int> num_to_index;
        int size = nums.size();

        for(int index = 0; index < size; index++) {
            int num = nums[index];

            if (num_to_index.contains(target - num)) {
                int the_other_index = num_to_index[target - num];
                return {the_other_index, index};
            }

            num_to_index[num] = index;
        }
        return {-1, -1};
    }
        
};

2. Simple Bank System

class Bank {
public:
    Bank(vector<long long>& balance) {

        this->balance_ = balance;
    }
    
    bool transfer(int account1, int account2, long long money) {
        if (!withdraw(account1, money)) {
            return false;
        }

        if (!deposit(account2, money)) {
            deposit(account1, money);
            return false;

        }

        return true;
    }
    
    bool deposit(int account, long long money) {

        if (!ValidAccount(account)) {
            return false;
        }

        balance_[account - 1] += money;

        return true;
    }
    
    bool withdraw(int account, long long money) {

        if (!ValidAccount(account)) {
            return false;
        }

        if (balance_[account - 1] < money) {
            return false;
        }

        balance_[account - 1] -= money;
        return true;
    }
private:
    bool ValidAccount(int account_num) {
        if (account_num < 1) {
            return false;
        }

        if (account_num > balance_.size()) {
            return false;
        }
        return true;
    }
    std::vector<long long> balance_;
};

/**
 * Your Bank object will be instantiated and called as such:
 * Bank* obj = new Bank(balance);
 * bool param_1 = obj->transfer(account1,account2,money);
 * bool param_2 = obj->deposit(account,money);
 * bool param_3 = obj->withdraw(account,money);
 */

3. Substring XOR queries

class Solution {
public:
    struct Index{
        int left;
        int right;
    };

    // Note: val ^ first = second is the same as finding val = first ^ second;
    vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
        std::vector<int> zero_indexes;
        std::vector<int> one_indexes;
        
        int size = s.size();

        for(int index = 0; index < size; index++) {
            if (s[index] == '1') {
                one_indexes.push_back(index);
                continue;
            }

            zero_indexes.push_back(index);
        }

        // Map of "value" obtained by evaluating substrings of (s) between (i and j).
        std::unordered_map<long long, Index> _map;

        if (!zero_indexes.empty()) {
            _map[0] = Index{
                .left = zero_indexes[0],
                .right = zero_indexes[0]
            };
        }

        // Instead of looping over all the indexes of s, we can loop over the the indexes where the value is 1
        for(auto i : one_indexes) {
            int running_val = 0;
            for(int j = i; j < std::min(size, i + 64); j++) {
                long long digit = 0;

                if(s[j] == '1') {
                    digit = 1;
                }
                running_val <<= 1;
                running_val |= digit;

                if (!_map.contains(running_val)) {
                    _map[running_val] = Index{
                        .left = i,
                        .right = j
                    };
                    continue;
                }

                int existing_len = _map[running_val].right - _map[running_val].left + 1;
                int current_len = j - i + 1;

                if (current_len < existing_len) {
                    _map[running_val] = Index{
                        .left = i,
                        .right = j
                    };
                    continue;
                }
            }
        }

        std::vector<std::vector<int>> answers;
        for(auto query : queries) {
            long long val = query[0] ^ query[1];

            if (!_map.contains(val)) {
                answers.push_back({-1, -1});
                continue;
            }


            Index indexes = _map[val];
            answers.push_back({
                indexes.left,
                indexes.right
            }
            );

            continue;
        }

        return answers;
    }
};

Flocela Maldonado

unread,

Oct 26, 2024, 2:31:30 PM10/26/24

to leetcode-meetup

Hi Daryl,

We're on the zoom meeting. Are you on the zoom meeting?

Gowrima Jayaramu

unread,

Oct 26, 2024, 2:42:24 PM10/26/24

to leetcode-meetup

# Time: O(n)
# Space = O(1)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        result = []

        for i in range(len(nums)):
            remaining = target-nums[i]
            
            for j in range(len(nums)):
                if nums[j] == remaining and i != j:
                    return i, j

Gowrima Jayaramu

unread,

Oct 26, 2024, 2:43:53 PM10/26/24

to leetcode-meetup

Sorry, time complexity is O(n^2).

# Time: O(n^2)

# Space = O(1)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []

        for i in range(len(nums)):
            remaining = target-nums[i]
            
            for j in range(len(nums)):
                if nums[j] == remaining and i != j:
                    return i, j

Flocela Maldonado

unread,

Oct 26, 2024, 2:47:44 PM10/26/24

to leetcode-meetup

First Saturday of the Month (Nov. 2nd) Coffee and Tea!

Join us for coffee and tea after the Zoom meeting (around 12:15pm)!

We meet at the library, Northside Branch Library (695 Moreland Way · Santa Clara, CA) and go to one of the coffee/lunch shops within walking distance.

-Flo

Sourabh Majumdar

unread,

Oct 27, 2024, 5:37:33 PM10/27/24

to leetcode-meetup

Awesome :D.

Look forward to it.

-Sourabh

Gowrima Jayaramu

unread,

Oct 27, 2024, 7:31:42 PM10/27/24

to leetcode-meetup

class Bank:

    def __init__(self, balance: List[int]):

        self.balance = balance

    def isValidTxn(self, account):
        if account < 1 or account > len(self.balance):
            return False
        
        return True

    def transfer(self, account1: int, account2: int, money: int) -> bool:
        

        if not self.isValidTxn(account1) or not self.isValidTxn(account2) or self.balance[account1-1]<money:
            return False
        
        self.balance[account1-1] = self.balance[account1-1] - money    
        self.balance[account2-1] = self.balance[account2-1] + money

        return True

    def deposit(self, account: int, money: int) -> bool:

        if not self.isValidTxn(account):
            return False

        self.balance[account-1] += money

        return True

    def withdraw(self, account: int, money: int) -> bool:

        if not self.isValidTxn(account) or self.balance[account-1] < money:
            return False

        self.balance[account-1] -= money

        return True


# Your Bank object will be instantiated and called as such:
# obj = Bank(balance)
# param_1 = obj.transfer(account1,account2,money)
# param_2 = obj.deposit(account,money)
# param_3 = obj.withdraw(account,money)

Reply all

Reply to author

Forward