maximum-gap.dart (1449B)
1 //Given a list of values find the max gap from one value 2 //to the next once the list is sorted. To do this I used 3 //merge sort to sort the list, then I checked every index to find 4 //the largest gap and returned it. The time complexity 5 //of this code is O(nlog(n)) because that is how long merge 6 //sort takes. 7 //Time: 676ms Beats: 20% 8 //Memory: 214MB Beats: 20% 9 class Solution { 10 int maximumGap(List<int> nums) { 11 nums = merge(nums); 12 int max_gap = 0; 13 for(int i = 1 ; i < nums.length ; ++i){ 14 if((nums[i] - nums[i - 1]).abs() > max_gap){ 15 max_gap = (nums[i] - nums[i - 1]).abs(); 16 } 17 } 18 return max_gap; 19 } 20 List<int> merge (List<int> nums){ 21 if(nums.length == 1){ 22 return nums; 23 } 24 List<int> l1 = merge(nums.sublist(0 , (nums.length / 2).toInt())); 25 List<int> l2 = merge(nums.sublist((nums.length / 2).toInt())); 26 int l1_ptr = 0; 27 int l2_ptr = 0; 28 List<int> l3 = []; 29 while( l1_ptr < l1.length && l2_ptr < l2.length ){ 30 if(l1[l1_ptr] < l2[l2_ptr]){ 31 l3.add(l1[l1_ptr]); 32 l1_ptr += 1; 33 } 34 else{ 35 l3.add(l2[l2_ptr]); 36 l2_ptr += 1; 37 } 38 } 39 while(l1_ptr < l1.length){ 40 l3.add(l1[l1_ptr]); 41 l1_ptr += 1; 42 } 43 while(l2_ptr < l2.length){ 44 l3.add(l2[l2_ptr]); 45 l2_ptr += 1; 46 } 47 return l3; 48 } 49 }