Minimum Time Difference - DP(ish) solution

-
Problem is here: https://leetcode.com/problems/minimum-time-difference/description/

Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimum minutes difference between any two time points in the list.
Example 1:
Input: ["23:59","00:00"]
Output: 1
Note:
  1. The number of time points in the given list is at least 2 and won't exceed 20000.
  2. The input time is legal and ranges from 00:00 to 23:59.
Despite being a medium-complexity problem, there is a way to do it in linear time using concepts of DP:

  • Basically the input range is very small: it fits into a 1500 array
  • Create a bool array of this size and map each time to it
  • If the time has already been set, return 0 (that's the min)
  • This cost linear time and constant space (O(1500))
  • Next traverse the array and compare the two adjacent cells that have a time on it
  • Some extra check is needed for the boundary case when the min diff crosses the day line
That's it! Cheers, Boris


public class Solution
{
 public int FindMinDifference(IList timePoints)
 {
  if (timePoints == null) return 0;

  bool[] map = new bool[1500];

  int min = Int32.MaxValue;
  int max = Int32.MinValue;
  foreach (string t in timePoints)
  {
   string[] parts = t.Split(':');
   int val = Int32.Parse(parts[0]) * 60 + Int32.Parse(parts[1]);

   if (map[val]) return 0;
   map[val] = true;

   min = Math.Min(min, val);
   max = Math.Max(max, val);
  }

  int solution = Math.Abs(24 * 60 - (max - min));
  int previousIndex = min;
  for (int i = min + 1; i < map.Length; i++)
  {
   if (map[i])
   {
    solution = Math.Min(solution, i - previousIndex);
    previousIndex = i;
   }
  }

  return solution;
 }
}

Comments

  1. TarasJanuary 7, 2019 at 7:32 PM

    Nicely done! Since the input size is so small, I've decided to use a sort-based approach:
    1) convert all times to minutes
    2) sort all the times
    3) find the minimum difference between 2 successive times and compare it with the corner case where the time between the largest and smallest times is the smallest. The code in Rust is below:

    impl Solution {
    pub fn find_min_difference(time_points: Vec) -> i32 {
    fn to_minutes(time: &str) -> i32 {
    let parts: Vec<_> = time.split(":").collect();
    let hours: i32 = parts[0].parse().unwrap();
    let minutes: i32 = parts[1].parse().unwrap();
    hours * 60 + minutes
    }
    let mut minutes: Vec<_> = time_points.iter().map(|t| to_minutes(&t)).collect();
    minutes.sort_unstable();
    std::cmp::min(
    minutes.iter().zip(minutes.iter().skip(1)).map(|(x, y)| y - x).min().unwrap(),
    minutes[0] + 1440 - minutes.last().unwrap(),
    )
    }
    }

    https://gist.github.com/ttsugriy/81bd95b2781a57065580789fba4f80a2

    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