2025 November 1 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 from last week.

485. Max Consecutive Ones Easy 63.5%

3592. Inverse Coin Change Medium 50.6%

3615. Longest Palindromic Path in Graph Hard 20.5%

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

[Anuj Patnaik]

class Solution:

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

curr_ct = 0

max_ct = 0

for i in range(len(nums)):

if nums[i] == 1:

curr_ct += 1

max_ct = max(curr_ct, max_ct)

else:

curr_ct = 0

return max_ct

[FloM]

485. Max Consecutive Ones Easy 63.5%

Time: O(n). Mem: O(1)

class Solution {

public:

int findMaxConsecutiveOnes(vector<int>& nums) {

int globalMax = 0;

int localMax = 0;

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

{

if (nums[ii] == 0)

{

globalMax = std::max(globalMax, localMax);

localMax = 0;

}

else

{

++localMax;

}

}

globalMax = std::max(globalMax, localMax);

return globalMax;

}

};

[Nightvid Cole]

class Solution:

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

        nums.append(0)

        maxOnes = 0

        zeroPos = -1

        for numIndex in range(0,len(nums)):

            num = nums[numIndex]

            if num < 1:

                onesLength = numIndex-zeroPos-1

                zeroPos = numIndex

                if onesLength > maxOnes:

                    maxOnes = onesLength

        return maxOnes

Time O(n)

Space O(n) [if input array is included] / O(1) [otherwise]

[Wang Lijun]

class Solution:

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

res = 0

count = 0

for i in range(len(nums)):

if nums[i] == 1:

count+=1

res = max(res, count)

else:

count = 0

return res

[Carrie Lastname]

Posted this last week but I'll post it again:

class Solution:
    def findCoins(self, numWays: List[int]) -> List[int]:
        ans = []
        dp = [0 for _ in range(len(numWays)+1)]
        dp[0] = 1
        while True:
            newdp = [1]
            curr = None
            for i,num in enumerate(numWays):
                if curr==None and dp[i+1] + newdp[0] == num:
                    # found new denomination
                    curr = i+1
                    ans.append(curr)
                if curr:
                    newdp.append(dp[i+1] + newdp[-curr])
                else:
                    newdp.append(dp[i+1])
            if curr == None:
                if newdp[1:] != numWays:
                    return []
                return ans                
            dp = newdp

On Saturday, November 1, 2025 at 9:42:11 AM UTC-7 daryl...@gmail.com wrote:

[Anuj Patnaik]

class Solution:

def findCoins(self, numWays: List[int]) -> List[int]:

numWays = [1] + numWays

dp = [0] * (len(numWays))

dp[0] = 1

coins = []

for i in range(1, len(numWays)):

if dp[i] < numWays[i]:

coins.append(i)

for j in range(i, len(numWays)):

dp[j] += dp[j - i]

if dp == numWays:

return coins

else:

return []

[Bhupathi Kakarlapudi]

class Solution {

public:

int findMaxConsecutiveOnes(vector<int>& nums) {

int max_ones = 0;

int cnt_ones = 0;

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

{

if(nums[i] == 1)

cnt_ones++;

else

{

max_ones = std::max(cnt_ones, max_ones);

cnt_ones = 0;

}

}

max_ones = std::max(cnt_ones, max_ones);

return max_ones;

}

};

--
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/4aaf3e26-5350-4058-90b3-7e486a7b6579n%40googlegroups.com.

[Marco Guadiana]

class Solution {

    public int findMaxConsecutiveOnes(int[] nums) {

        int maxOnes = 0;  

        int currentOnes = 0;

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

            if (nums[i] == 1) {

                currentOnes++;  

                maxOnes = Math.max(maxOnes, currentOnes);  

            } else {

                currentOnes = 0;  

            }

        }

        return maxOnes;

    }

}

On Saturday, November 1, 2025 at 9:42:11 AM UTC-7 daryl...@gmail.com wrote:

[Allen S.]

func findMaxConsecutiveOnes(nums []int) int {

count := 0

res := 0

for i := range nums {

if nums[i] == 1 {

count++

} else {

count = 0

}

res = max(res, count)

}

return res

}

On Saturday, November 1, 2025 at 9:42:11 AM UTC-7 daryl...@gmail.com wrote:

[Sourabh Majumdar]

class Solution {

public:

    int findMaxConsecutiveOnes(vector<int>& nums) {

        int count_ones = 0;

        int max_ones = 0;

        for(auto value : nums) {

            if (value == 1) {

                count_ones += 1;

                continue;

            }

            max_ones = std::max(

                max_ones,

                count_ones

            );

            count_ones = 0;

        }

        max_ones = std::max(

            max_ones,

            count_ones

        );

        return max_ones;

    }

};

[FloM]

3615. Longest Palindromic Path in Graph Hard 20.5%

Time: O(n^3) Mem: O(n?)

class Solution {

public:

uint32_t getLength(

uint32_t nodeA,

uint32_t nodeB,

vector<vector<uint32_t>>& adjList,

string& label,

uint32_t & marked,

unordered_map<uint32_t, uint32_t>& memoPad

)

{

// Key is made up of nodeA, nodeB, and the set of nodes that are already in the palindrome.

uint32_t small = std::min(nodeA, nodeB);

uint32_t large = std::max(nodeA, nodeB);

uint32_t key = (100000000 * small) + (100000 * large) + marked;

if (memoPad.contains(key))

{

return memoPad[key];

}

if (label[nodeA] != label[nodeB] || nodeA == nodeB)

{

memoPad.insert({key, 0});

return memoPad[key];

}

uint32_t selfCount = 2; // Count NodeA and NodeB, they definitely match and are not the same node.

uint32_t maxCount = 0;

// For each combination of adjacent nodes to NodeA and NodeB call getLength().

for(uint32_t aaNIdx=0; aaNIdx<adjList[nodeA].size(); ++aaNIdx)

{

uint32_t aaNode = adjList[nodeA][aaNIdx];

if (inContainer(marked, aaNode)) { continue; }

insertIntoContainer(marked, aaNode);

for(uint32_t bbNIdx=0; bbNIdx<adjList[nodeB].size(); ++bbNIdx)

{

uint32_t bbNode = adjList[nodeB][bbNIdx];

if (inContainer(marked, bbNode)) {continue;}

insertIntoContainer(marked, bbNode);

uint32_t curCount = getLength(aaNode, bbNode, adjList, label, marked, memoPad);

maxCount = std::max(maxCount, curCount);

eraseFromContainer(marked, bbNode);

}

eraseFromContainer(marked, aaNode);

}

memoPad.insert({key, (maxCount + selfCount)});

return memoPad[key];

}

void insertIntoContainer(uint32_t& container, uint32_t number)

{

container |= (1 << number);

}

void eraseFromContainer(uint32_t& container, uint32_t number)

{

container &= (~( 1 << number));

}

bool inContainer(const uint32_t& container, const uint32_t& number)

{

return ( (container) & (1 << number)) > 0;

}

int maxLen(int n, vector<vector<int>>& edges, string label) {

// Longest palindrome length given the key as a uint32_t.

// The key is the sum of two nodes to be placed in the palidrome and the set of nodes that are already in the palindrome.

// The set of nodes that are already in the palindrome are represented by seen, a uint32_t.

unordered_map<uint32_t, uint32_t> memoPad{};

// adjaceny list.

vector<vector<uint32_t>> adjList(n, vector<uint32_t>{});

for(const vector<int>& edge : edges)

{

adjList[edge[0]].push_back(edge[1]);

adjList[edge[1]].push_back(edge[0]);

}

// nodeB is central node in the palindrome.

// Case where the palindrome length is odd. Take each letter (nodeB), put it in the container seen (which holds all the nodes in the palindrome).

// Take all combinations of adjacent letters to nodeB and call getLength().

uint32_t seen = 0;

uint32_t maxCount = 1; // Count nodeB as 1. May be a palindrome of length one.

for(uint32_t nodeB=0; nodeB<n; ++nodeB)

{

insertIntoContainer(seen, nodeB);

for(uint32_t ii=0; ii<adjList[nodeB].size(); ++ii)

{

uint32_t nodeA = adjList[nodeB][ii];

insertIntoContainer(seen, nodeA);

for(uint32_t jj=ii+1; jj<adjList[nodeB].size(); ++jj)

{

uint32_t nodeC = adjList[nodeB][jj];

insertIntoContainer(seen, nodeC);

uint32_t count = getLength(nodeA, nodeC, adjList, label, seen, memoPad);

eraseFromContainer(seen, nodeC);

maxCount = std::max(maxCount, count + 1);

}

eraseFromContainer(seen, nodeA);

}

eraseFromContainer(seen, nodeB);

}

// Find the longest length if there is no center of palindrome.

for(uint32_t nodeA=0; nodeA<n; ++nodeA)

{

insertIntoContainer(seen, nodeA);

for(uint32_t ii=0; ii<adjList[nodeA].size(); ++ii)

{

uint32_t nodeB = adjList[nodeA][ii];

insertIntoContainer(seen, nodeB);

uint32_t count = getLength(nodeA, nodeB, adjList, label, seen, memoPad);

eraseFromContainer(seen, nodeB);

maxCount = std::max(maxCount, count);

}

eraseFromContainer(seen, nodeA);

}

return maxCount;

}

};

[FloM]

3592. Inverse Coin Change Medium 50.6%

Not my solution, but easy to understand

class Solution {

public:

vector<int> findCoins(vector<int>& dp) {

int n = dp.size();

dp.insert(dp.begin(), 1); // prepend dp[0] = 1

vector<int> res;

for (int a = 1; a <= n; ++a) {

if (dp[a] > 1) return {};

if (dp[a] == 0) continue;

res.push_back(a);

for (int v = n; v >= a; --v) {

dp[v] -= dp[v - a];

if (dp[v] < 0) return {};

}

}

return res;

}

};