On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).

Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.

You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?

Example 1:


Input: [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.

You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.


Example 2:


Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:
 0  1  2  3  4
24 23 22 21  5
12 13 14 15 16
11 17 18 19 20
10  9  8  7  6

The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.


Note:


       2 <= N <= 50.
       grid[i][j] is a permutation of [0, ..., N*N - 1].

Difficulty: interview

Starter code:

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        

Solutions:
from collections import Counter
 
 
 class Solution:
     def reorganizeString(self, S):
         """
         :type S: str
         :rtype: str
         """
         if len(S) <= 1:
             return S
 
         chars = [char for char, count in Counter(S).most_common() for _ in range(count)]
         h = math.ceil(len(chars) / 2)
         chars[::2], chars[1::2] = chars[:h], chars[h:]
         if chars[0] == chars[1]:
             return ''
         else:
             return ''.join(chars)
         
         

class Solution:
     def reorganizeString(self, S):
         """
         :type S: str
         :rtype: str
         """
         counter = collections.Counter(S)
         h = [(-v, k) for k, v in list(counter.items())]
         heapq.heapify(h)
         ans = []
         while h:
             v, c = heapq.heappop(h)
             ans.append(c)
             counter[c] -= 1
             if len(ans) >= 2:
                 ch = ans[-2]
                 if counter[ch] > 0:
                     heapq.heappush(h, (-counter[ch], ch))
         if len(ans) < len(S):
             return ""
         return ''.join(ans)


import collections
 
 
 def reorganize(s):
 
     counts = collections.Counter(s)
     output = []
     last_char = None
 
 
     while counts:
 
         for c, count in sorted(counts.items(), key=lambda x:x[1], reverse=True):
             if output and c == output[-1]:
                 if len(counts) == 1:
                     #  return "".join(output)
                     return ""
             else:
                 output.append(c)
                 counts[c] -= 1
                 if counts[c] == 0:
                     counts.pop(c)
                 break
 
     return "".join(output)
 
 
 
 class Solution:
     def reorganizeString(self, S):
         """
         :type S: str
         :rtype: str
         """
         return reorganize(S)

import queue
 
 class CountPair:
     def __init__(self, key, count):
         self.key = key
         self.count = count
     def __lt__(self, other):
         return self.count > other.count
 
 class Solution:
     def reorganizeString(self, S):
         """
         :type S: str
         :rtype: str
         """
         c_hash = {}
         q = queue.PriorityQueue()
         for c in S:
             if c not in c_hash:
                 c_hash[c] = 1
             else:
                 c_hash[c] += 1
         for k in c_hash:
             tmp = CountPair(k,c_hash[k])
             q.put(tmp)
         result = "#"
         for i in range(len(S)):
             v = q.get()
             if v.count==0:
                 return ""
             if result[-1] != v.key:
                 result += v.key
                 v.count -= 1
                 if v.count != 0:
                     q.put(v)
             else:
                 if q.empty():
                     return ""
                 v2 = q.get()
                 result += v2.key
                 v2.count -= 1
                 if v2.count != 0:
                     q.put(v2)
                 q.put(v)
         return result[1:]
             
                 
         
         
         
         
         
         
         
         

class Solution:
     def reorganizeString(self, S):
         """
         :type S: str
         :rtype: str
         """
         from math import ceil
         dict1 = {}
         s = ""
         for i in range(len(S)):
             if S[i] not in dict1:
                 dict1[S[i]] = 1
             else:
                 dict1[S[i]] += 1
             if dict1[S[i]] > ceil(len(S)/2): return ""
         dict2 = [ item for item in list(dict1.items())]
         dict2.sort(key=lambda x:x[1], reverse=True)
         for i in range(dict2[0][1]):
             s = s + dict2[0][0]
         for i in range(1,len(dict2)):
             temp = 0
             value =  dict2[i][1]
             key = dict2[i][0]
             while value>0:
                 for j in range(i):
                     while value > 0 and (dict2[j][0]+ dict2[j][0]) in s:
                         s = s[0:s.index(dict2[j][0]+ dict2[j][0])] + dict2[j][0]+ key + dict2[j][0] + s[s.index(dict2[j][0]+ dict2[j][0])+2:]
                         value -= 1
                 if value>0:
                     if key in s:
                         temp = s.index(key)
                         if temp>=2:
                             s = s[0:temp-2] + key + s[temp-2:]
                         else:
                             s = key + s
                         value -= 1
                     else:
                         s = s + key
                         value -= 1
         return s


from collections import Counter
 class Solution:
     def reorganizeString(self, S):
         """
         :type S: str
         :rtype: str
         """
         count = Counter(S)
         mylist = count.most_common()
         _, maxfreq = mylist[0]
 
         if maxfreq > (len(S) + 1) // 2:
             return ""
         else:
             res = [[] for _ in range(maxfreq)]
             start = 0
             for char, freq in mylist:
                 for i in range(freq):
                     res[(i + start) % maxfreq].append(char)
                 start += freq
             return "".join("".join(temp) for temp in res)

class Solution:
     def reorganizeString(self, S):
         """
         :type S: str
         :rtype: str
         """
         
         # pq = [(-S.count(x), x) for x in set(S)]
         count = {}
         limit = (len(S) + 1) / 2
         for c in S:
             if c in count:
                 count[c] += 1
             else:
                 count[c] = 1
                 
             if (count[c] > limit):
                 return("")
         
         pq = []
         for x in count.keys():
             c = count[x]
             pq.append((-c, x))    
         
         
         # pq = []
         # limit = (len(S) + 1) / 2
         # for x in set(S):
         #     count = S.count(x)
         #     if (count > limit):
         #         return("")
         #     pq.append((-count, x))
         
         heapq.heapify(pq)
         
         result = []
         while len(pq) >= 2:
             count1, char1 = heapq.heappop(pq)
             count2, char2 = heapq.heappop(pq)
             result.extend([char1, char2])
             
             if (count1 != -1): 
                 heapq.heappush(pq, (count1 + 1, char1))
             if (count2 != -1): 
                 heapq.heappush(pq, (count2 + 1, char2))
 
         answer = "".join(result) 
         if (len(pq) == 1):
             answer += heapq.heappop(pq)[1]
         
         return(answer)

from collections import Counter
 from math import ceil
 class Solution:
     def reorganizeString(self, S):
         """
         :type S: str
         :rtype: str
         """
         char_freq = Counter(S).most_common()
         max_freq = char_freq[0][-1]
         
         if max_freq > ceil(len(S)/2):
             return ''
         else:
             buckets = [[] for _ in range(max_freq)]
             print(char_freq)
             start = 0 
             for char,freq in char_freq:
                 print(char,freq)
                 for i in range(freq):
                     idx = (i+start)%max_freq
                     print(idx)
                     buckets[idx].append(char)
                 start+=freq
             
             return ''.join(''.join(bucket) for bucket in buckets)
         
         

from itertools import groupby
 class Solution:
     def reorganizeString(self, s):
         """
         :type d: str
         :rtype: str
         """
         counts = sorted([s.count(x) for x in set(s)] + [0])[::-1]
         
         if counts[0] > sum(counts[1:]) + 1:
             return ""
         
         gl = sorted([list(j) for i, j in groupby(sorted(list(s)))], key=lambda x: -len(x))
         
         res = ""
         while gl:
             
             res += gl[0].pop()
             if len(gl) > 1:
                 res += gl[1].pop()
 
             gl = list(filter(None, gl))
             gl.sort(key=lambda x: -len(x))
         return res
         
         

from itertools import groupby
 class Solution:
     def reorganizeString(self, s):
         """
         :type d: str
         :rtype: str
         """
         counts = sorted([s.count(x) for x in set(s)] + [0])[::-1]
         
         if counts[0] > sum(counts[1:]) + 1:
             return ""
         
         gl = sorted([list(j) for i, j in groupby(sorted(list(s)))], key=lambda x: -len(x))
         
         res = ""
         while gl:
             
             res += gl[0].pop()
             if len(gl) > 1:
                 res += gl[1].pop()
 
             gl = list(filter(None, gl))
             gl.sort(key=lambda x: -len(x))
         return res
         
         

class Solution(object):
     def reorganizeString(self, S):
         N = len(S)
         A = []
         for c, x in sorted((S.count(x), x) for x in set(S)):
             if c > (N+1)/2: return ""
             A.extend(c * x)
             print(A)
         ans = [None] * N
         ans[::2], ans[1::2] = A[int(N/2):], A[:int(N/2)]
         print(ans[::2])
         return "".join(ans)

class Solution:
     def reorganizeString(self, S):
         c = collections.Counter(S)
         if max(c.values()) <= (len(S) + 1) / 2:
             res = ""
             while c:
                 out = c.most_common(2)
                 if len(out):
                     res += out[0][0]
                     c[out[0][0]] -= 1
                 if len(out) > 1:
                     res += out[1][0]
                     c[out[1][0]] -= 1
                 c += collections.Counter()
             return res
         return ""
         """
         :type S: str
         :rtype: str
         """

class Solution:
     def reorganizeString(self, S):
         """
         :type S: str
         :rtype: str
         """
         '''
         size = len(S)
         limit = size//2 + size%2
         cnt = collections.Counter(S)
         res = [0]*size
         i = 0
         for k, v in cnt.most_common():
             if v > limit:
                 return ''
             for _ in range(v):
                 if i >= size:
                     i = res.index(0)
                 res[i] = k
                 i += 2
         return ''.join(res)
         '''
         cnt = collections.Counter(S)
         res = '#'
         while cnt:
             stop = True
             for k, v in cnt.most_common():
                 if k != res[-1]:
                     stop = False
                     res += k
                     cnt[k] -= 1
                     if not cnt[k]:
                         del cnt[k]
                     break
             if stop == True:
                 break
         return res[1:] if len(res) == len(S)+1 else ''


null