When TLE happened and a test case is given, it only means that the TLE happened while executing that test case.
It's possible that your solution took too much time during previous test cases and this case is just the last straw.
dasheng2
@dasheng2
Posts made by dasheng2

RE: Could some Python expert help me explain this, please!

Share my fast Python solution based on Newton's method
Based on Newton's method. Optimizations for performance:
 start from num/2 + 1;
 use a variable to store the calculated square to save one redundant calculation
class Solution(object): def isPerfectSquare(self, num): """ :type num: int :rtype: bool """ ''' Newton's method f(x) = x^2  n > f'(x) = 2x x1 = x0  f(x0)/f'(x0) = x0  (x0^2  n) / (2x0) x1 = (x0^2 + n) / (2x0), or x1 = (x0 + n/x0)/2 ''' root = (num >> 1) + 1 while True: square = root * root if square > num: root = (root + num/root) >> 1 else: break return square == num

RE: Python Accepted Solution
Inspired by u, I made some changes and the run time is improved to ~330 ms.
Consider it as a shortest path problem . See my explanation in the code.
The main performance improvement comes from using nondecreasing sequence of square numbers.
e.g., when checking 13, for the two possible sequences (4, 9) and (9, 4) only the former is checked.class Solution(object): def numSquares(self, n): """ :type n: int :rtype: int """ distance, q1, q2, label = 1, [(0, 1)], [], [10] * (n + 1) ''' Shortest Path Imagine a graph whose vertices are numbers from 0 to n. The lengths of all edges are 1. Two vertices differ by any perfect square numbers are connected. Starting from vertex 0, the shortest path to reach vertex n is the answer. Since the length of all edges are the same, we can use a queue instead of heap to store the vertices to be explored in each step. Another improvement is that we only check nondecreasing sequence of square numbers, e.g.: 13 > (4, 9), not (9, 4) ''' while True: for node, length in q1: # nondecreasing sequence only for edge in xrange(length, n+1): next_node = node + edge*edge if next_node == n: return distance elif next_node > n: break elif label[next_node] > distance: label[next_node] = distance # add node and the edge used last q2.append((next_node, edge)) q1, q2 = q2, [] distance += 1

RE: Python O(NlogN) solution
It is O(n^2), not O(NlogN).
min(ends) and max(ends) are called within a for loop and the length of ends can be in the order of N.
The list ends is sorted so you can just use ends[0] and ends[1] to get O(NlogN)

RE: Integral image solution, 156ms. I know I know, it's slow, just want to throw it out here
Your idea is good but the code needs optimization.
After generating the summed area table, we can scan the table row by row, checking if there is any square satisfying the square area condition. Once we found one, we can increase the maxSize by 1 and check next row. The optimized version has running time of 12 ms.
class Solution { public: int maximalSquare(vector<vector<char>>& matrix) { int rows = matrix.size(); if (rows == 0) return 0; int cols = matrix[0].size(); if (cols == 0) return 0; int val; vector < vector<int> > image(rows+1, vector <int> (cols+1, 0)); // Integral image for (int r = 1; r <= rows; r++) { for (int c = 1; c <= cols; c++) { val = (matrix[r1][c1] == '0' ? 0 : 1); image[r][c] = val + image[r][c1] + image[r1][c]  image[r1][c1]; } } if (image[rows][cols] == 0) return 0; int maxSize = 1; for (int r = 2; r <= rows; r++){ int next = maxSize + 1; int area = next*next; for (int c = next; c <= cols; c++){ if (image[r][c] + image[rnext][cnext]  image[r][cnext]  image[rnext][c] == area) { maxSize = next; break; } } } return maxSize * maxSize; } };
And the Python version:
class Solution(object): def maximalSquare(self, matrix): """ :type matrix: List[List[str]] :rtype: int """ rows, max_size = len(matrix), 0 if rows > 0: cols = len(matrix[0]) ''' Use summed area table to calculate maximal square The value at image[x][y] is the sum of all elements above and to the left of (x1, y1) in matrix (converted to int) The area of rectangle ABDC (top left > top right > bottom right > bottom left), as below A B C D is image[D] + image[A]  image[B]  image[C] We can scan the summed area table, check if the area of a squre is exactly the square of the length of edge ''' image = [[0] * (cols+1) for _ in range(rows+1)] # generate summedarea table for x in xrange(rows): for y in xrange(cols): image[x+1][y+1] = image[x+1][y] + image[x][y+1]  image[x][y] + (1 if matrix[x][y] == '1' else 0) if image[rows][cols] > 0: max_size = 1 for x in xrange(2, rows+1): # next_size: next possible maximal size of square next_size = max_size + 1 area = next_size*next_size for y in xrange(next_size, cols+1): # check the area of squares if (image[x][y] + image[xnext_size][ynext_size]  image[x][ynext_size]  image[xnext_size][y] == area): max_size = next_size break; return max_size*max_size

RE: Python 80ms DP solution beats 100% O(mn) time one pass
Great idea!
I've changed your code a little. I think it is more concise and easier to understand
class Solution(object): def maximalSquare(self, matrix): """ :type matrix: List[List[str]] :rtype: int """ rows, max_size = len(matrix), 0 ''' size[i]: the current number of continuous '1's in a column of matrix. Reset when discontinued. The idea is to do a byrow scan, updating size[i] Then check if there are continuous elements in size whose value is bigger than current maximal size. ''' if rows > 0: cols = len(matrix[0]) size = [0] * cols for x in xrange(rows): # update size count, size = 0, map(lambda x, y: x+1 if y == '1' else 0, size, matrix[x]) for y in xrange(cols): # check if it exceeds current maximal size if size[y] > max_size: count += 1 if count > max_size: # increase maximal size by 1 max_size += 1 break else: count = 0 return max_size*max_size

Share my Python solution, O(n) for init and O(1) for query
Use an extra element for summation so we don't need to check boundary condition in the query.
class NumArray(object): def __init__(self, nums): """ initialize your data structure here. :type nums: List[int] """ self.sums = [0] * (len(nums) + 1) for i in xrange(len(nums)): self.sums[i+1] = self.sums[i] + nums[i] def sumRange(self, i, j): """ sum of elements nums[i..j], inclusive. :type i: int :type j: int :rtype: int """ return self.sums[j+1]  self.sums[i]

Share my Python solution using RMQ
The idea is based on the article on geeksforgeeks. I made changes for the method to find the maximum rectangular area. The original is a recursive function, which will reach maximum stack depth for Python. So I've changed it into an iterative one. Time complexity is O(NlogN).
import math class Solution(object): def largestRectangleArea(self, height): """ :type height: List[int] :rtype: int """ def _RMQHelper(height, segment_tree, start, end, query_start, query_end, node_index): ''' helper function to get the index of minimum value in a given range of indice. height: List[int], the input list for which segment tree is built segment_tree: List[int], the segment tree start, end: int, starting / ending indice of segment represented by current node, segment_tree[node_index] query_start, query_end: int, starting and ending indice of query range index: int, index of current node in the segment tree. root is always at index 0 ''' if (query_start <= start) and (query_end >= end): # segment of this node is part of query range, return the minimum of the segment return segment_tree[node_index] if (query_start > end) or (query_end < start): # segment of this node is outside the query range return 1 # part of this segment overlaps with the query range, check left and right part recursively middle = (start + end) >> 1 left = _RMQHelper(height, segment_tree, start, middle, query_start, query_end, (node_index<<1) + 1) right = _RMQHelper(height, segment_tree, middle+1, end, query_start, query_end, (node_index<<1) + 2) if left == 1: return right elif right == 1: return left return left if height[left] < height[right] else right # range minimum query to get index of minimum element in range [query_start, query_end] def _RMQ(height, segment_tree, query_start, query_end): return _RMQHelper(height, segment_tree, 0, len(height)1, query_start, query_end, 0) # find the maximum rectangular area in range [query_start, query_end] def _getMaxAreaHelper(height, segment_tree, query_start, query_end): stack, max_area = [(query_start, query_end)], 0 # need to use stack to avoid stack depth overflow while stack: query_start, query_end = stack.pop() if query_start == query_end: # only one bar in the range if height[query_start] > max_area: max_area = height[query_start] else: # get the index of lowest bar in the given range min_index = _RMQ(height, segment_tree, query_start, query_end) # calculate rectangle area including the lowest bar area = (query_end  query_start + 1) * height[min_index] if area > max_area: max_area = area # push endpoints of left and right halves onto stack if query_start < min_index: stack.append((query_start, min_index  1)) if query_end > min_index: stack.append((min_index + 1, query_end)) return max_area length = len(height) if length > 0: # Build segment tree from height segment_tree = self.constructST(height) return _getMaxAreaHelper(height, segment_tree, 0, length1) else: return 0 # construct segment tree def constructST(self, height): # helper def _constructSTHelper(height, segment_tree, start, end, node_index): if start == end: # If there is only one element in array, store it in the current node segment_tree[node_index] = start else: # recursively scan left and right subtrees and store the minimum of the two values in this node middle = (start + end) >> 1 left = _constructSTHelper(height, segment_tree, start, middle, (node_index<<1) + 1) right = _constructSTHelper(height, segment_tree, middle+1, end, (node_index<<1) + 2) segment_tree[node_index] = left if height[left] < height[right] else right return segment_tree[node_index] # build segment tree length = len(height) segment_tree = [0] * (2**(int(math.ceil(math.log(length, 2))) + 1)  1) _constructSTHelper(height, segment_tree, 0, length1, 0) return segment_tree

RE: HELP... Different results between run code and submit.
The problem lies here:
for(int i = 0 ; i <= height.size() ; i++){ if(index.empty()  height[index.back()] <= height[i] ){ ....
when i equals to height.size(), accessing height[i] causes array index outofbound. That's why you have different results for "submit" and "run code".
First you need to use i < height.size() in the for loop. You can also append a '0' at the end of height, so you don't need to worry about if anything is left in the stack.
The following code got AC
class Solution { public: int largestRectangleArea(vector<int>& height) { vector<int> index; int res = 0; height.push_back(0); // guard for(int i = 0 ; i < height.size() ; i++){ if(index.empty()  height[index.back()] <= height[i] ){ index.push_back(i); } else{ while(!index.empty() && height[index.back()] > height[i]){ //if current number is smaller, calculate the biggest area so far int h = height[index.back()]; index.pop_back(); int leftindex = index.empty() ? 1 : index.back(); //between leftindx and i is larger than h res = max(res, h*(i  leftindex1)); } index.push_back(i); } } return res; } };