2025 September 13 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.

Problem 2845 has been carried over.

Please post your solutions to this thread so others can use this as a reference.

3633. Earliest Finish Time for Land and Water Rides I Easy 61.0%

2845. Count of Interesting Subarrays Medium 58.0%

3572. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values 62.6%

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 maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:

possible_indices = dict()

for i in range(len(x)):

if x[i] in possible_indices:

if y[i] > y[possible_indices[x[i]]]:

possible_indices[x[i]] = i

else:

possible_indices[x[i]] = i

max_y = []

for j in possible_indices.values():

max_y.append(y[j])

if len(max_y) < 3:

return -1

else:

max_y.sort()

rev_max_y = max_y[::-1]

return rev_max_y[0] + rev_max_y[1] + rev_max_y[2]

[Kevin Burleigh]

3572. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values 62.6%

## Time: O(n)

## Memory: O(n)

class Solution:

def maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:

idxs_by_x_val = defaultdict(list)

for idx,val in enumerate(x):

idxs_by_x_val[val].append(idx)

if len(idxs_by_x_val) < 3:

return -1

max_y_val_by_x_val = defaultdict(int)

for val,idxs in idxs_by_x_val.items():

for idx in idxs:

max_y_val_by_x_val[val] = max(max_y_val_by_x_val[val], y[idx])

y_minheap = []

for val in max_y_val_by_x_val.values():

if len(y_minheap) >= 3:

if val > y_minheap[0]:

heappop(y_minheap)

heappush(y_minheap, val)

else:

heappush(y_minheap, val)

return sum(y_minheap)

[Allen S.]

func earliestFinishTime(landStartTime []int, landDuration []int, waterStartTime []int, waterDuration []int) int {

landWater := earliestFinishTimeInOrder(landStartTime, landDuration, waterStartTime, waterDuration)

waterLand := earliestFinishTimeInOrder(waterStartTime, waterDuration, landStartTime, landDuration)

return min(landWater, waterLand)

}

func earliestFinishTimeInOrder(start1, duration1, start2, duration2 []int) int {

earliestFinishTime1 := math.MaxInt

for i := range start1 {

earliestFinishTime1 = min(earliestFinishTime1, start1[i] + duration1[i])

}

result := math.MaxInt

for i := range start2 {

result = min(result, max(earliestFinishTime1, start2[i])+ duration2[i])

}

return result

}

[Eli Manzo]

Hey Everyone! First time submitting a solution. Excited to learn a lot more about DSA and meet some cool people!

# Time: O(n^2)

# Space: O(1)

class Solution:

  def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:

    res = float("inf")

    n = len(landStartTime)

    m = len(waterStartTime)

    for i in range(n):

      landFinishTime = landStartTime[i] + landDuration[i]

      for j in range(m):

        waterFinishTime = waterStartTime[j] + waterDuration[j]

        startWater = max(landFinishTime, waterStartTime[j])

        landFirstFinishTime = startWater + waterDuration[j]

        startLand = max(waterFinishTime, landStartTime[i])

        waterFirstFinishTime = startLand + landDuration[i]

        res = min(res, landFirstFinishTime, waterFirstFinishTime)

    return res

       

On Saturday, September 13, 2025 at 10:24:03 AM UTC-7 Kevin Burleigh wrote:

[Anuj Patnaik]

class Solution:

def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:

min_time = float('inf')

l_finish = float('inf')

w_finish = float('inf')

#Land_to_Water

for i in range(len(landStartTime)):

l_finish = min(l_finish, landStartTime[i] + landDuration[i])

for j in range(len(waterStartTime)):

min_time = min(min_time, max(l_finish, waterStartTime[j]) + waterDuration[j])

#Water_to_Land

for m in range(len(waterStartTime)):

w_finish = min(w_finish, waterStartTime[m] + waterDuration[m])

for n in range(len(landStartTime)):

min_time = min(min_time, max(w_finish, landStartTime[n]) + landDuration[n])

return min_time

[Kevin Burleigh]

## Brute force:

##

## foreach pair of possible subarray start/end indices (l_idx,r_idx): ## O(N^2)

## foreach elem in nums[l_idx:r_idx+1]: ## O(N)

## if elem % m == k:

## elem_count += 1

## if elem_count % m == k:

## interesting_count += 1

## return interesting_count

##

## We are counting and re-counting the same subsets of elems. Use the

## difference of cumsum values instead:

##

## target_elems_to_left = [0]*(1+N_nums)

## for idx,elem in enumerate(nums):

## if elem % m == k:

## target_elems_to_left[1+idx] += 1

## else:

## target_elems_to_left[1+idx] = target_elems_to_left[idx]

##

## foreach pair of possible subarray start/end indices (l_idx,r_idx): ## O(N^2)

## elem_count = target_elems_to_left[1+r_idx] - target_elems_to_left[l_idx] ## O(1)

## if elem_count % m == k:

## interesting_count += 1

## return interesting_count

##

## 0 1 2 3 4 5 6 7 8 idx

## 3 1 4 1 5 9 2 6 5 elems, m=3 k=2

## 0 1 1 1 2 0 2 0 2 elem % m

## 0 0 0 0 1 0 1 0 1 elem % m == k

## 0 0 0 0 1 1 2 2 3 cumsum

## 0 0 0 0 1 1 2 2 0 cumsum % k

## -------------

## -----------

## ---------

## -------

## -----

## ---------------

## -------------

## -----------

## ---------

## -------

## --------

## ------

##

## Some observations:

## (1) If the cumsum up to and including the current elem % m == k,

## then the subarray starting at index 0 and ending with

## the current elem is one we should count.

## (2) For every remainder p, there is another remainder q (the "complement")

## such that (r - q) % m == k.

## (3) Using (2), we can "subtract off" subarrays that have q elems

## to construct new arrays that have % m == k elems

## (4) If we save the counts as we go, we can reuse them in (3).

## (5) Foreach remainder p, we only need the most recent count.

## (6) Instead of searching for the count for p, we can use a map to quicky find it.

## Time: O(n) n = len(nums)

## Space: O(n)

class Solution:

def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:

count_by_mod = defaultdict(int)

cs_mod = 0

result = 0

for num in nums:

if num % modulo == k:

cs_mod = (cs_mod + 1) % modulo

if cs_mod == k:

result += 1

cs_comp = (cs_mod - k) % modulo

result += count_by_mod[cs_comp]

count_by_mod[cs_mod] += 1

return result

[FloM]

3633. Earliest Finish Time for Land and Water Rides I Easy 61.0%

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

class Solution {

public:

// eStart is earliest start

int earliestFinish(int eStart, vector<int>& startTimes, vector<int>& durations)

{

int eFinish = 3000;

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

{

int startTime = startTimes[ii];

int duration = durations[ii];

int endTime = startTime + durations[ii];

if (startTime >= eStart)

{

eFinish = std::min(eFinish, startTime + duration);

}

else

{

eFinish = std::min(eFinish, eStart + duration);

}

}

return eFinish;

}

int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration, vector<int>& waterStartTime, vector<int>& waterDuration) {

// Start with Land

int earliestLandFinishA = earliestFinish(0, landStartTime, landDuration);

int earliestWaterFinishA = earliestFinish(earliestLandFinishA, waterStartTime, waterDuration);

// Start with Water

int earliestWaterFinishB = earliestFinish(0, waterStartTime, waterDuration);

int earliestLandFinishB = earliestFinish(earliestWaterFinishB, landStartTime, landDuration);

return std::min(earliestWaterFinishA, earliestLandFinishB);

}

};

[FloM]

3572. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values 62.6%

Time: O(n), Mem O(1), one vector size 3

class Solution {

public:

int maxSumDistinctTriplet(vector<int>& x, vector<int>& y) {

vector<vector<int>> ordered(3, vector<int>{-1, -1});

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

{

int xVal = x[ii];

int yVal = y[ii];

if (yVal < ordered[0][1])

{

continue;

}

if ((ordered[1][0] != xVal) && (ordered[2][0] != xVal))

{

ordered[0][0] = xVal;

ordered[0][1] = yVal;

sort(ordered.begin(), ordered.end(), [](const vector<int>& a, const vector<int>& b){return a[1] < b[1];});

}

else if ( ((ordered[1][0]) == xVal) && (ordered[1][1] < yVal) )

{

ordered[1][1] = yVal;

sort(ordered.begin(), ordered.end(), [](const vector<int>& a, const vector<int>& b){return a[1] < b[1];});

}

else if (ordered[2][1] < yVal)

{

ordered[2][1] = yVal;

sort(ordered.begin(), ordered.end(), [](const vector<int>& a, const vector<int>& b){return a[1] < b[1];});

}

}

if (ordered[0][0] == -1)

{

return -1;

}

else

{

return ordered[0][1] + ordered[1][1] + ordered[2][1];

}

}

};