You’re given an array, people, where people[i] is the weight of the ith person, and an infinite number of boats, where each boat can carry a maximum weight, limit. Each boat carries, at most, two people at the same time. This is provided that the sum of the weight of those people is under or equal to the weight limit. You need to return the mini…

rescue-boats.js

// people is an array of numbers, each number represents a person's weight
// limit is the max weight of a boat
// the number of boats is unlimited
// find minimum number of boats
export function rescueBoats(people, limit) {
  // sort people by weight
  people.sort();

  // set first pointer to point at the lightest person
  let light = 0;
  // set second pointer to point at the heaviest person
  let heavy = people.length - 1;
  // init our result (number of boats)
  let boats = 0;

  // repeat until our pointers meet
  while (light <= heavy) {
    if (people[light] + people[heavy] <= limit) {
      // if both persons (lightest and heaviest) fit into a boat,
      // move both pointers towards each other and increment number of boats
      boats += 1;
      light += 1;
      heavy -= 1;
    } else {
      // otherwise only the heaviest person goes into the boat
      boats += 1;
      heavy -= 1;
    }
  }
  
  return boats;
}

// complexity of the while loop is O(n) however we sort the array so overall it's O(n + nlogn). Space complexity is O(n) because of sorting.