I feel like the time complexity should be mn time to find all 1's , then for each 1, we go through mn time to calculate distance at each empty space(0). Thus, it is m*n + k mn . Could that reach upper bound of m^2n^2?
F
fiona8957
@fiona8957
1
Reputation
6
Posts
176
Profile views
0
Followers
0
Following
Posts made by fiona8957

RE: Java solution with explanation and time complexity analysis

RE: My simple java Solution use recursion
Isn't the time complexity o(nklogn) where k is avg length of linked list??

Swift solution got TLE
I can't identify what the problem is. Can anyone please help me with this issue?
class Solution { func insertionSortList(_ head: ListNode?) > ListNode? { if head == nil  head?.next == nil { return head } let dummy = ListNode(Int.min) var prev = dummy var cur = head while cur != nil { let next = cur?.next prev = dummy while prev.next != nil && prev.next!.val < cur!.val { prev = prev.next! } cur?.next = prev.next prev.next = cur cur = next } return dummy.next }

RE: About the swift version TLE
I had the same issue before. It was caused by calculating the length of each string multiple times in the second loop. Just precalculate and store the length of each string in an array and that works.