wangchi1989
BAN USERThe same solution as yours, written in C++
// time complexity: O(n^2)
int maxAreaInMatrix(vector<vector<int> > &matrix)
{
// check input
int height = matrix.size();
assert(height > 0);
int width = matrix[0].size();
assert(width > 0);
for (int i = 0; i < height; i++) assert(width == matrix[i].size());
vector<int> histogram(width, 0);
int maxArea = 0;
for (int h = 0; h < height; h++)
{
for (int i = 0; i < width; i++)
{
histogram[i] = (matrix[h][i] == 0) ? 0 : histogram[i] + 1;
}
int tempArea = maxAreaInHistogram(histogram);
if (tempArea > maxArea) maxArea = tempArea;
}
return maxArea;
}
// time complexity: O(n)
int maxAreaInHistogram(vector<int> &histogram)
{
int length = histogram.size();
assert(length > 0);
stack<int> heightStack;
heightStack.push(0);
stack<int> indexStack;
indexStack.push(-1);
int maxArea = 0;
for (int i = 0; i < length; i++)
{
int curHeight = histogram[i];
if (curHeight > heightStack.top())
{
heightStack.push(curHeight);
indexStack.push(i);
}
else if (curHeight == heightStack.top())
{
// do nothing
}
else
{
int topHeight = heightStack.top();
int topIndex;
while (curHeight < topHeight)
{
topIndex = indexStack.top();
int tempArea = topHeight * (i - topIndex);
if (tempArea > maxArea) maxArea = tempArea;
heightStack.pop();
indexStack.pop();
topHeight = heightStack.top();
}
if (curHeight > topHeight)
{
heightStack.push(curHeight);
indexStack.push(topIndex);
}
}
}
while (!heightStack.empty())
{
int tempArea = heightStack.top() * (length - indexStack.top());
if (tempArea > maxArea) maxArea = tempArea;
heightStack.pop();
indexStack.pop();
}
return maxArea;
}
Use an array of length (L1 + L2) to store the result, where L1 is the length of num1, while L2 is the length of num2.
// implemented in C++
// implementation of singly linked list node
class ListNode
{
public:
int val;
ListNode* next;
ListNode() {}
ListNode(int v) : val(v), next(NULL) {}
~ListNode() {}
};
// global array used to store result and its length
int* buffer = NULL;
int lenBuffer = 0;
ListNode* multiply(ListNode* num1, ListNode* num2)
{
if (num1 == NULL || num2 == NULL) return NULL;
int length1 = lengthOfNumber(num1);
int length2 = lengthOfNumber(num2);
if (length1 > length2) return multiply(num2, num1);
// initialize buffer
lenBuffer = length1 + length2;
buffer = new int[lenBuffer];
memset(buffer, 0, sizeof(int) * lenBuffer);
// multiply
int offset = 0;
ListNode* node = num1;
while (node)
{
multiplyHelper(node->val, num2, offset);
node = node->next;
offset++;
}
// transfer buffer to a linked list
ListNode* head = NULL;
int pos = 0;
while (pos < lenBuffer && buffer[pos] == 0) pos++;
if (pos < lenBuffer)
{
head = new ListNode(buffer[pos++]);
node = head;
while (pos < lenBuffer)
{
node->next = new ListNode(buffer[pos++]);
node = node->next;
}
}
delete buffer;
lenBuffer = 0;
buffer = NULL;
return head;
}
// multiply a single digit with a number
// called by multiply()
void multiplyHelper(int value, ListNode* head, int offset)
{
assert(value >= 0 && value <= 9 && head != NULL);
if (value == 0) return;
ListNode* node = head;
int pos = 0;
while (node)
{
int temp = value * node->val;
int ones = temp % 10;
if (ones != 0) addToBuffer(ones, offset + pos + 1);
int tens = temp / 10;
if (tens != 0) addToBuffer(tens, offset + pos);
node = node->next;
pos++;
}
}
// add a single digit to the buffer at place of index
// called by multiplyHelper()
void addToBuffer(int value, int index)
{
assert(value >= 0 && value <= 9);
while (value > 0 && index >= 0)
{
int temp = buffer[index] + value;
buffer[index] = temp % 10;
value = temp / 10;
index--;
}
}
int lengthOfNumber(ListNode* num)
{
assert(num != NULL);
ListNode* node = num;
int len = 0;
while (node)
{
len++;
node = node->next;
}
return len;
}
A relatively simple solution. The space complexity would be O(L1 + L2). The time complexity would be between O(n^2) and O(n^3). I'm not quite sure about that since I couldn't decide the time complexity of addToBuffer().
- wangchi1989 March 18, 2014
For each element, trace it down until a loop is formed.
e.g. [2, 3, 1, 0]
1. all add one ==> [3, 4, 2, 1]
2. at position 0
arr[0] = arr[arr[0] - 1] = arr[3 - 1] = arr[2]
so, we swap position 0 and 2, and maintain a integer "value" to remember what arr[2] is originally
Here we get:
- new arr: [-2, 4, 3, 1] (-2 is to mark it's in right place)
- value: 2 (what arr[2] is originally)
then we at the position 2,
arr[2] = arr[arr[2] - 1] = arr[value - 1] = arr[1]
then we swap position 2 and 1, and update "value" to arr[1]
new arr: [-2, 3, -4, 1]
value: 4
then we at position 1
as before, we get
new arr: [-2, -1, -4, 3]
value: 1
then we at position 3
arr[3] = arr[arr[3] - 1] = arr[value - 1] = arr[0]
since arr[0] now is negative, we've finished this loop, set current position to its opposite and move to next position.
Now arr = [-2, -1, -4, -3]
3. since all values are negative, they're in right places. Restore value, we get:
[-2, -1, -4, -3] ==> [2, 1, 4, 3] ==> [1, 0, 3, 2]
4. done
- wangchi1989 March 22, 2014