2024 March 9 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.

I decided to roll over last week's hard problem. We had one solution after the fact, and everyone else can try to take a crack at it.

2154Keep Multiplying Found Values by Two71.4%Easy

2285Maximum Total Importance of Roads60.9%Medium

2551Put Marbles in Bags66.8%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

[Flocela Maldonado]

2154Keep Multiplying Found Values by Two71.4%Easy

Time: O(n); Memory O(n)

 class Solution {

public:

int findFinalValue(vector<int>& nums, int original) {

unordered_set<int> values{};

for (int n : nums)

{

values.insert(n);

}

int cur = original;

int ans = cur;

while ( values.find(cur) != values.end() )

{

ans += cur;

cur = 2 * cur;

}

return ans;

}

};

[Flocela Maldonado]

2285Maximum Total Importance of Roads60.9%Medium

Time: O(n*lg(n) + r)
Memory: O(n)

Where n is the number of nodes, and r is the number of roads.

class Solution {

public:

long long maximumImportance(int n, vector<vector<int>>& roads) {

//At each index, pair is {index, number of connecting edges}

vector<pair<int, int>> nodeNumberAndNumOfEdges(n, pair<int,int>{0,0});

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

{

nodeNumberAndNumOfEdges[ii] = pair<int, int>{ii, 0};

}

// populate nodeNumberAndNumOfEdges with roads from roads vector

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

{

int u = roads[ii][0];

int v = roads[ii][1];

int countAtU = nodeNumberAndNumOfEdges[u].second;

nodeNumberAndNumOfEdges[u] = {u, ++countAtU};

int countAtV = nodeNumberAndNumOfEdges[v].second;

nodeNumberAndNumOfEdges[v] = {v, ++countAtV};

}

sort(nodeNumberAndNumOfEdges.begin(), nodeNumberAndNumOfEdges.end(), [](pair<int, int>& a, pair<int, int>& b){

return a.second < b.second;

});

// least important node is at the beginning of vector, assign it an importance of 1

// Assign each node an importance number based on their index in nodeNumberAndNumOfEdges

long long importance = 0;

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

{

long long temp = static_cast<long long>(ii+1) * nodeNumberAndNumOfEdges[ii].second;

importance += temp;

}

return importance;

}

};

On Saturday, March 9, 2024 at 10:26:20 AM UTC-8 Sumedh Guha wrote:

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        hash = {}
        for n in nums:
            hash[n] = 1
        while original in hash:
            original *= 2
        return original

On Saturday, March 9, 2024 at 9:36:25 AM UTC-8 daryl...@gmail.com wrote:

[Flocela Maldonado]

2551Put Marbles in Bags66.8%Hard

Time: O(n * lg(n)) Memory: O(n)class Solution {

public:

long long putMarbles(vector<int>& weights, int k) {

int n = weights.size();

// pairs. Each pair's second value is the partition's index. The partition is to the right of the index.

// Each pair's first value is the sum of the two numbers to the left and right of the partition.

// So a pair would be {weights[ii] + weights[ii+1], ii}

vector<vector<int>> sumAndPIndexes{};

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

{

sumAndPIndexes.push_back({weights[ii]+weights[ii+1], ii});

}

// The pairs are sorted in increasing order per each pair's first value. The first value is the partition's sum.

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

// the k-1 partitions that have the largest sums. The sum is the weight at the two indexes to the left and right of the partition.

// find these at the right end of the sorted sumAndPIndexes.

vector<int> partitionIndexesForMaximumScore{};

int idx = sumAndPIndexes.size()-1;

for (int ii=0; ii<k-1; ++ii)

{

partitionIndexesForMaximumScore.push_back(sumAndPIndexes[idx][1]);

--idx;

}

// the k-1 partitions that have the smallest sums.

// find these at the left end of the sorted sumAndPIndexes.

vector<int> partitionIndexesForMinimumScore{};

idx = 0;

for (int ii=0; ii<k-1; ++ii)

{

partitionIndexesForMinimumScore.push_back(sumAndPIndexes[idx][1]);

++idx;

}

// maxSum is the sum over the top k-1 partitions plus the weight at weight[0] and weight[n-1]

long long maxSum = weights[0];

maxSum += weights[n-1];

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

{

int partitionIndex = partitionIndexesForMaximumScore[ii];

maxSum += weights[partitionIndex];

maxSum += weights[partitionIndex+1];

}

// minSum is the sum over the bottom k-1 partitions plus the weight at weight[0] and weight[n-1]

long long minSum = weights[0];

minSum += weights[n-1];

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

{

int partitionIndex = partitionIndexesForMinimumScore[ii];

minSum += weights[partitionIndex];

minSum += weights[partitionIndex+1];

}

return std::abs(maxSum - minSum);

}

};

[daryl...@gmail.com]

2285Maximum Total Importance of Roads60.9%Medium

Count up the number of times each city appears in a road, and then assign importance to cities in order of their appearances.

Just returning the total sum makes the problem a lot easier since the sort doesn't need to keep track of city identity.

O(nlog(n)) time

O(n) space

func maximumImportance(n int, roads [][]int) int64 {

var ans int64

counts := make(sort.IntSlice, n)

for _, road := range roads {

counts[road[0]] += 1

counts[road[1]] += 1

}

sort.Sort(counts)

for i, count := range(counts) {

ans += int64(i + 1) * int64(count)

}

return ans

}

On Saturday, March 9, 2024 at 9:36:25 AM UTC-8 daryl...@gmail.com wrote:

[Sumedh Guha]

'''
Objectives:
Look for original in nums.
When found, multiply original by 2.
Keep searching for original until we can't find anymore.
Return original.

Questions:
What if we have duplicates? Just keep multiplying original by 2x.

Approaches:

Approach #1:
Same as objective.
O(n^2). Search could be linear.

Approach #2:
Use hash to store all nums values.
Search through hash.
O(n)

Tests:

nums=[5,3,6,1,12]
original=3

hash =
{
    1 : 1,
    3 : 1,
    5 : 1,
    6 : 1,
    12 : 1,
}
original=3
original=6
original=12
original=24
'''

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        hash = {}
        for n in nums:
            hash[n] = 1
        while original in hash:
            original *= 2
        return original

[Priyank Gupta]

# Time : O(N)

# Space: O(N)

class Solution:

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

numSet = set()

for num in nums:

numSet.add(num)

while(original in numSet):

original = 2*original

return original

[vinay]

2285Maximum Total Importance of Roads60.9%Medium

Assign the rank on the nodes based on indegree and then compute the importance of roads

time complexity for sorting - O(nlogn)

space o(n)

class Solution {

    public long maximumImportance(int n, int[][] roads) {

        //heavily connected cities should get higher number

        //least lower

        Map<Integer,Integer> map = new HashMap<>();

        int rank = 1;

        long importance = 0;

        for(int[] road : roads){

            int from = road[0];

            int to = road[1];

            map.put(from, map.getOrDefault(from,0)+1);

            map.put(to, map.getOrDefault(to,0)+1);

        }

       

        List<Map.Entry<Integer,Integer>> list = new ArrayList(map.entrySet());

        Collections.sort(list, (a,b) -> Integer.compare(b.getValue(), a.getValue()));

       

        //update the map with integer assigned

        for(Map.Entry<Integer,Integer> item : list){

            int key = item.getKey();

            map.put(key, n);

            n--;

        }

 

        for(int[] road : roads){

            int from = road[0];

            int to = road[1];

            importance += map.get(from) + map.get(to);

        }

        return importance;

    }

}

--
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/4b84bbc4-20bc-495b-8cec-e92b6f1b1192n%40googlegroups.com.

[vinay]

2154Keep Multiplying Found Values by Two71.4%Easy

time complexity: O(n log n)

space: o log(n) for sorting

class Solution {

    public int findFinalValue(int[] nums, int original) {

        Arrays.sort(nums);

        while(Arrays.binarySearch(nums, original) >= 0){

            original *= 2;

        }

        return original;

    }

}

[Vivek H]

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

2154Keep Multiplying Found Values by Two71.4%Easy

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

Time complexity = O(n) + log(n) = O(n)

Space complexity = O(n)

class Solution {

public:

    int findFinalValue(vector<int>& nums, int original) {

        set<int> S;

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

            S.insert(nums[i]);

        }

        int final;

        while(true) {

            if(S.find(original) != S.end()) {

                original = 2*original;

            } else {

                break;

            }

        }

        return original;

    }

};

On Sat, Mar 9, 2024 at 9:36 AM daryl...@gmail.com <daryl...@gmail.com> wrote:

--

[Vivek H]

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

2285Maximum Total Importance of Roads60.9%Medium

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

Time complexity = O(vertex + edges)

Space complexity = O(vertex + edges)

class Solution {

public:

    struct comp {

        bool operator()(const pair<int, int>& p1,

                        const pair<int, int>& p2) const {

            if (p1.second == p2.second) {

                return p1.first < p2.first;

            }

            return p1.second > p2.second;

        }

    };

    map<int, vector<int>> G;

    long long maximumImportance(int n, vector<vector<int>>& roads) {

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

            G[i] = {};

        }

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

            G[roads[i][0]].push_back(roads[i][1]);

            G[roads[i][1]].push_back(roads[i][0]);

        }

        set<pair<int, int>, comp> S;

        for (auto& a : G) {

            S.insert({a.first, a.second.size()});

        }

        map<int, int> points;

        long long total = 0;

        for (auto it = S.begin(); it != S.end(); it++) {

            //cout << "it->first:" << it->first << " n:" << n << endl;

            points[it->first] = n;

            n--;

        }

        for (auto& a : points) {

            for (int i = 0; i < G[a.first].size(); i++) {

                //cout << a.second << "+" << points[G[a.first][i]] << endl;

                total += (a.second + points[G[a.first][i]]);

            }

        }

        //cout << "total:" << total << endl;

        return total/2;

    }

};

On Sat, Mar 9, 2024 at 9:36 AM daryl...@gmail.com <daryl...@gmail.com> wrote:

--