remove() is O(Log(k)), but remove(Object) is O(k) sadly. I had the same idea at first...
E
eran
@eran
14
Reputation
9
Posts
226
Profile views
0
Followers
0
Following
Posts made by eran

RE: My Java Solution Using PriorityQueue

RE: 15ms Concise Java Solution
Can you please explain point #4? how is matrix[x][y] <= matrix[i][j] avoids needing a visited[m][n] array, sorry for the silly question :)

RE: Python binary search solution  O(logn)  48ms
mid = (low + high) / 2 can get you integer overflow, I prefer mid = low + (highlow)/2

Share my easy to understand AC recursive python solution (52 ms, 83.84%)
class Solution(object): def subsets(self, nums): if not nums: return [[]] head, tail = nums[0], nums[1:] smaller = self.subsets(tail) ret = [] for item in smaller: ret.append(item) ret.append( sorted(item + [head])) return ret

My easy to read accepted Java solution O(N) time, O(1) additional memory
I guess I had the same idea as others, it might be a lesser O(N) than the turtle and hare approach to find the middle, but it might be easier to reason about.
public class Solution { public boolean isPalindrome(ListNode head) { //base cases if (head == null  head.next == null) { return true; } //find the length int l = length(head); //the ceil of the half is the rightofmiddle element (we ignore the middle one if it's an odd length) int half = l/2 + (l%2==0?0:1); //there are more elegant ways but this is most readable I think) //get the middle node (not as efficient as turtle and hare, but perhaps more readable) ListNode halfNode = nodeAt(head, half); //reverse from the middle to the end ListNode halfReversed = reverse(halfNode); //check the two halves are equal... return isEqual(head, halfReversed); } public boolean isEqual(ListNode head1, ListNode head2){ //checks that two halves are equal (assumes they are of the same length, in real world while(head1 != null && head2 != null && head1 != head2) { if (head1.val != head2.val) { return false; } head1 = head1.next; head2 = head2.next; } //in the real world we should have checked: return head1 == null && head2 == null; return true; } public ListNode nodeAt(ListNode head, int index) { int ret = 0; while(head != null && ret < index) { head = head.next; ret++; } return head; } public int length(ListNode head) { int ret = 0; while(head != null) { head = head.next; ret++; } return ret; } public ListNode reverse(ListNode head) { ListNode prev = null; ListNode cur = head; while(cur != null){ ListNode tempNext = cur.next; cur.next = prev; prev = cur; cur = tempNext; } return prev; } }

RE: Short Python...
Can you please post a blog / video explaining?