[Two Pointers] LC 881. Boats to Save People

  • Given an array people where people[i] is the weight of the ith person, and an infinite number of boats
  • Each boat carries at most two people at the same time
  • Return the minimum number of boats to carry every given person.
  • Set the left = 0, and right = n-1
  • The right pointer is moving at a constant speed: 1 to the left every iteration, given the fact that our worst case scenario is using exactly n boats
  • We are moving the left pointer to break the constant speed → while left < right, and decrease the number of boat used
  • A greedy approach by adding up the largest & smallest element
  • A type of pointer problem with left and right moving toward the opposite direction
  • Strong hint of using greedy
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
people.sort()

l, r = 0, len(people)-1
res=0

while l<=r:
res+=1
if people[l] + people[r] <=limit:
l+=1
r-=1
return res

--

--

--

Data Engineering & Analytics

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

CS 373 Spring 2022: William Eng, Week 3

Create Your First Linux Server on AWS EC2

Brute Force Approach to Algorithms

Code-First vs. SQL-First

Books that helped me learn Python, fast.

Concerns of SMBs on DMARC

How to Reset Zigo Eon 62i

reset my phone

Responsive images and progressive image loading with laravel

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Iris S

Iris S

Data Engineering & Analytics

More from Medium

Comparison between Bubble Sort and Selection Sort

Decompression

A screenshot of an internet browser window with many, many tabs open along the top, with underneath the words ‘you have too many tabs open.’

Why Development Cooperation Needs to Tackle Underlying Issues of Inequality First

Needfinding: Flight check-in experience