Maximize Distance to Closest Person, two-scans solution

-
Problem is here: https://leetcode.com/problems/maximize-distance-to-closest-person/description/

In a row of seats, 1 represents a person sitting in that seat, and 0 represents that the seat is empty. 
There is at least one empty seat, and at least one person sitting.
Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized. 
Return that maximum distance to closest person.
Example 1:
Input: [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.
Example 2:
Input: [1,0,0,0]
Output: 3
Explanation: 
If Alex sits in the last seat, the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.
Note:
  1. 1 <= seats.length <= 20000
  2. seats contains only 0s or 1s, at least one 0, and at least one 1.

The easiest way to solve this problem is to do two scans: first go from L => R and set the min distance from an empty seat to a taken seat. Then move the other direction, R => L, doing the same thing. But, in the second pass (since it is the last), keep track of the max distance too. O(n)-space, O(n)-time. Cheers, Boris.



public class Solution
{
 public int MaxDistToClosest(int[] seats)
 {
  int[] min = new int[seats.Length];
  int oo = Int32.MaxValue;

  //Base
  for (int i = 0; i < min.Length; i++) min[i] = oo;

  //"Construction"
  int max = 0;

  //1.L->R
  int anchor = -1;
  for (int i = 0; i < min.Length; i++)
  {
   if (seats[i] == 1) anchor = i;
   else if (anchor != -1) min[i] = Math.Min(min[i], i - anchor);
  }

  //2.R->L
  anchor = -1;
  for (int i = min.Length - 1; i >= 0; i--)
  {
   if (seats[i] == 1) anchor = i;
   else if (anchor != -1) min[i] = Math.Min(min[i], anchor - i);
   max = (min[i] != oo) ? Math.Max(max, min[i]) : max;
  }

  return max;
 }
}

Comments

  1. TarasDecember 22, 2018 at 9:27 PM

    It's interesting to see how many different ways are there to think about this problem. I thought about it in a following way - there are 3 cases to consider - sitting at the very left or very right seat or between 2 other chairs. First 2 can be found by doing a linear search for the very first taken seat and the last case can be handled by finding the biggest "gap" between 2 chairs and dividing it by 2:

    class Solution:
    def maxDistToClosest(self, seats):
    """
    :type seats: List[int]
    :rtype: int
    """
    max_gap, current_gap = 0, 0
    for seat in seats:
    current_gap = 0 if seat == 1 else current_gap + 1
    max_gap = max(max_gap, current_gap)
    return max(seats.index(1), math.ceil(max_gap / 2), seats[::-1].index(1))

    This results in O(N) time and O(1) space complexity.

    Cheers,
    Taras

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more