online advertising

Wednesday, May 9, 2018

LeetCode OJ - Can Place Flowers

Problem:

Please find the problem here.

Solution:

The key hint in this problem is that it is an easy problem. That lead me to think about greedy algorithm.

The idea is simple, we simply start from the left and plant a flower whenever we can. The key challenge, however, is to prove that this idea is optimal.

Analysis:

We will use the greedy algorithm stay ahead method.

First, we know that there exist an optimal solution, we claim that our greedy algorithm is going to be at least as good as the optimal algorithm for every prefix.

It is obvious for prefix of length 0, both of them has planted 0 plants.

Assuming the invariant held for all prefixes of length $ k $. Is it possible for the greedy algorithm to lose for $ k + 1 $?

For the sake of argument, we assume that the optimal wins at position $ k + 1 $. The only possibility for $ k + 1 $ to win is that in the optimal solution we planted but in the greedy algorithm we didn't.

Note that if the optimal solution can plant in location $ k + 1 $, then the location $ k $ and $ k + 2 $ must be empty (initially and also in the optimal solution)

The only reason that the greedy algorithm cannot plant in location $ k + 1 $ is because $ k $ is already planted. But we already argued that in the optimal solution location $ k $ is empty in the optimal solution, so we have a situation like this

        k           (k + 1)
Greedy  planted     not planted
Optimal not planted planted

So the number of plants in both greedy and optimal is the same for the last two, but we already knew that any prefixes cannot win, so the fact that the optimal solution wins at position $ k + 1 $ is a contradiction.

The contradiction shows that any prefix of the greedy solution is better than the optimal. Since the whole problem is also a prefix, now we have just shown the correctness of the greedy algorithm!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/can-place-flowers

#include "LEET_CAN_PLACE_FLOWERS.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_CAN_PLACE_FLOWERS
{
    class Solution
    {
    public:
        bool canPlaceFlowers(vector<int>& flowerbed, int n)
        {
            for (size_t i = 0; i < flowerbed.size(); i++)
            {
                if (n == 0)
                {
                    break;
                }
                else
                {
                    if ((i == 0 || flowerbed[i - 1] == 0) && flowerbed[i] == 0 && ((i == flowerbed.size() - 1) || flowerbed[i + 1] == 0))
                    {
                        flowerbed[i] = 1;
                        n--;
                    }
                }
            }
            return n == 0;
        }
    };
};

using namespace _LEET_CAN_PLACE_FLOWERS;

int LEET_CAN_PLACE_FLOWERS()
{
    Solution solution;
    int test_array[] = { 1, 0, 0, 0, 1 };
    vector<int> test(test_array, test_array + _countof(test_array));
    cout << solution.canPlaceFlowers(test, 1) << endl;
    return 0;
}

Sunday, May 6, 2018

LeetCode OJ - Network Delay Time

Problem:

Please find the problem here.

Solution:

This is obviously a single source shortest path problem. Dijkstra's algorithm worked great for this problem.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/network-delay-time

#include "LEET_NETWORK_DELAY_TIME.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_NETWORK_DELAY_TIME
{
    class Solution
    {
    public:
        int networkDelayTime(vector<vector<int>>& times, int N, int K)
        {
            vector<int> heap;
            vector<int> node_to_heap_index;
            vector<int> heap_to_node_index;
            vector<bool> visited;
            int heap_size;
            vector<vector<pair<int, int>>> adjacency_list;

            // Step 1: Build the graph
            adjacency_list.resize(N);
            for (size_t i = 0; i < times.size(); i++)
            {
                // Make the node number start from 0
                int src = times[i][0] - 1;
                int dst = times[i][1] - 1;
                int time = times[i][2];
                adjacency_list[src].push_back(make_pair(dst, time));
            }

            // Step 2: Initialize the Dijkstra's algorithm
            heap.resize(N);
            node_to_heap_index.resize(N);
            heap_to_node_index.resize(N);
            visited.resize(N);
            for (int i = 0; i < N; i++)
            {
                visited[i] = false;
                node_to_heap_index[i] = -1;
            }

            heap[0] = 0;
            node_to_heap_index[K - 1] = 0;
            heap_to_node_index[0] = K - 1;
            heap_size = 1;
            
            int visit_count = 0;
            int last_visit_time;

            while (heap_size > 0)
            {
                int visiting_node = heap_to_node_index[0];
                int visiting_time = heap[0];
                visited[visiting_node] = true;
                last_visit_time = visiting_time;
                visit_count++;

                int last_node = heap_to_node_index[heap_size - 1];
                int last_time = heap[heap_size - 1];

                heap_size--;
                heap_to_node_index[0] = last_node;
                node_to_heap_index[last_node] = 0;
                heap[0] = last_time;

                int stone_heap_index = 0;
                while (true)
                {
                    bool swapped = false;
                    int stone_node = heap_to_node_index[stone_heap_index];
                    int stone_time = heap[stone_heap_index];
                    int left_heap_index = (stone_heap_index + 1) * 2 - 1;
                    int right_heap_index = left_heap_index + 1;
                    if (right_heap_index < heap_size)
                    {
                        int left_time = heap[left_heap_index];
                        int left_node = heap_to_node_index[left_heap_index];
                        int right_time = heap[right_heap_index];
                        int right_node = heap_to_node_index[right_heap_index];
                        if (left_time < right_time)
                        {
                            if (left_time < stone_time)
                            {
                                node_to_heap_index[stone_node] = left_heap_index;
                                heap_to_node_index[left_heap_index] = stone_node;
                                heap[left_heap_index] = stone_time;

                                node_to_heap_index[left_node] = stone_heap_index;
                                heap_to_node_index[stone_heap_index] = left_node;
                                heap[stone_heap_index] = left_time;

                                stone_heap_index = left_heap_index;
                                swapped = true;
                            }
                        }
                        else
                        {
                            if (right_time < stone_time)
                            {
                                node_to_heap_index[stone_node] = right_heap_index;
                                heap_to_node_index[right_heap_index] = stone_node;
                                heap[right_heap_index] = stone_time;

                                node_to_heap_index[right_node] = stone_heap_index;
                                heap_to_node_index[stone_heap_index] = right_node;
                                heap[stone_heap_index] = right_time;

                                stone_heap_index = right_heap_index;
                                swapped = true;
                            }
                        }
                    }
                    else if (left_heap_index < heap_size)
                    {
                        int left_time = heap[left_heap_index];
                        int left_node = heap_to_node_index[left_heap_index];
                        if (left_time < stone_time)
                        {
                            node_to_heap_index[stone_node] = left_heap_index;
                            heap_to_node_index[left_heap_index] = stone_node;
                            heap[left_heap_index] = stone_time;

                            node_to_heap_index[left_node] = stone_heap_index;
                            heap_to_node_index[stone_heap_index] = left_node;
                            heap[stone_heap_index] = left_time;

                            stone_heap_index = left_heap_index;
                            swapped = true;
                        }
                    }
                    if (!swapped)
                    {
                        break;
                    }
                }

                for (auto neighbor : adjacency_list[visiting_node])
                {
                    int neighbor_node = neighbor.first;
                    int neighbor_dist = neighbor.second;
                    int neighbor_time = visiting_time + neighbor_dist;
                    if (!visited[neighbor_node])
                    {
                        int bubble_heap_index;
                        if (node_to_heap_index[neighbor_node] == -1)
                        {
                            heap[heap_size] = neighbor_time;
                            heap_to_node_index[heap_size] = neighbor_node;
                            node_to_heap_index[neighbor_node] = heap_size;
                            
                            heap_size++;
                            bubble_heap_index = heap_size - 1;
                        }
                        else
                        {
                            bubble_heap_index = node_to_heap_index[neighbor_node];
                            if (heap[bubble_heap_index] > neighbor_time)
                            {
                                heap[bubble_heap_index] = neighbor_time;
                            }
                        }
                        while (true)
                        {
                            bool swapped = false;
                            if (bubble_heap_index > 0)
                            {
                                int bubble_node = heap_to_node_index[bubble_heap_index];
                                int bubble_time = heap[bubble_heap_index];
                                int parent_heap_index = bubble_heap_index / 2;
                                int parent_node = heap_to_node_index[parent_heap_index];
                                int parent_time = heap[parent_heap_index];
                                if (bubble_time < parent_time)
                                {
                                    node_to_heap_index[bubble_node] = parent_heap_index;
                                    heap_to_node_index[parent_heap_index] = bubble_node;
                                    heap[parent_heap_index] = bubble_time;

                                    node_to_heap_index[parent_node] = bubble_heap_index;
                                    heap_to_node_index[bubble_heap_index] = parent_node;
                                    heap[bubble_heap_index] = parent_time;

                                    bubble_heap_index = parent_heap_index;
                                    swapped = true;
                                }
                            }
                            if (!swapped)
                            {
                                break;
                            }
                        }
                    }
                }
            }
            if (visit_count == N)
            {
                return last_visit_time;
            }
            else
            {
                return -1;
            }
        }
    };
};

using namespace _LEET_NETWORK_DELAY_TIME;

int LEET_NETWORK_DELAY_TIME()
{
    // [[2,1,1],[2,3,1],[3,4,1]]
    Solution solution;
    vector<vector<int>> problem;
    problem.resize(3);
    problem[0].push_back(2);    problem[0].push_back(1);    problem[0].push_back(1);
    problem[1].push_back(2);    problem[1].push_back(3);    problem[1].push_back(1);
    problem[2].push_back(3);    problem[2].push_back(4);    problem[2].push_back(1);
    cout << solution.networkDelayTime(problem, 4, 2) << endl;
    return 0;
}

Tuesday, May 1, 2018

LeetCode OJ - Teemo Attacking

Problem:

Please find the problem here.

Solution:

I modeled the problem after line sweeping. We maintain an event queue. If the person is not poisoned, we dequeue an element from the timeSeries and make it poisoned (by noting the poison start time), enqueue an event after duration that it will recover. The enqueue is done implicitly by having a single separate variable named recover. If the next event is the recover, we account for the poisoned time. If the next event is an attack, then we postpone the recover event (simply by modifying the recover variable) and move on until there are no more events.

The line sweep way thinking helped me a big way to organize the code.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/teemo-attacking

#include "LEET_TEEMO_ATTACKING.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_TEEMO_ATTACKING
{
    class Solution {
    public:
        int findPoisonedDuration(vector<int>& timeSeries, int duration) {
            int result = 0;

            int poisoned = -1;
            int next = 0;
            int recover = -1;
            while (true)
            {
                if (poisoned == -1)
                {
                    if (next == timeSeries.size())
                    {
                        break;
                    }
                    poisoned = timeSeries[next];
                    recover = timeSeries[next] + duration;
                    next++;
                }
                else
                {
                    if ((next == timeSeries.size()) || (recover <= timeSeries[next]))
                    {
                        result += recover - poisoned;
                        poisoned = -1;
                    }
                    else
                    {
                        recover = timeSeries[next] + duration;
                        next++;
                    }
                }
            }
            return result;
        }
    };
};

using namespace _LEET_TEEMO_ATTACKING;

int LEET_TEEMO_ATTACKING()
{
    Solution solution;
    int test1_array[] = { 1, 4 };
    vector<int> test1(test1_array, test1_array + _countof(test1_array));
    cout << solution.findPoisonedDuration(test1, 2) << endl;
    int test2_array[] = { 1, 2 };
    vector<int> test2(test2_array, test2_array + _countof(test2_array));
    cout << solution.findPoisonedDuration(test2, 2) << endl;
    return 0;
}

LeetCode OJ - Remove Boxes

Problem:

Please find the problem here.

Analysis:

I will address the problem using interval dynamic programming. The key idea is that we build up the "answer" of interval of increasing length.

The "answer" for a length 1 interval is trivial. The key problem is how do we construct the "answer" for a particular length (k + 1) with the "answers" of all length k or below interval.

The "answers" are all in quotes, because we will see that the answer is just not the number of points obtained by removing boxes.

I have four key observations:

It make no sense to split a contiguous color by removing it in more than one step.

This observation is obvious, suppose we have a contiguous sequence of length (a + b), removing them together yield $ a^2 + 2ab + b^2 $, always better than $ a^2 + b^2 $.

Whatever the optimal plan of removable is, we can always transform the plan such that the last element is removed last.

Suppose the last element is removed in step 'k' and there are 'x' more steps after the step 'k'. The 'x' more steps must be removing something that is on the left of the last element continuous sequence. Therefore, we can swap such that the last element is removed last, without hurting the quality of the solution.

It is possible to get an optimal solution for (k+1) boxes from an non-optimal solution solving the earlier k boxes. 

Let assume the added box has the same color as the original last box.

Suppose we have a planA that is optimal for solving the first k boxes, and then we add one box to it. Given observation 1 - the newly added box must be removed at the same time the original last box is removed, and by observation 2, that move can be made the last step, so the points of planA', the plan of removing the (k+1) boxes, has points planA - (lastMoveALength)^2 + (lastMoveALength+1)^2 = planA + 2lastMoveALength + 1.

Similarly we can apply the same logic to planB, which is NOT optimal for solving the first k boxes, so we have points of planB' = planB + 2lastMoveBLength + 1.

Note that it is possible for planB' > planA' even when planA > planB because

planB' - planA' = (planB + 2lastMoveBLength + 1) - (planA + 2lastMoveALength + 1)

And obviously it could be bigger than 0 if lastMoveBLength > lastMoveALength by sufficient amount.

That make sense, because if you make a longer streak of the last color, it get better result, but this observation is also bad news because we can't assume the best plan is assembled by best plan.

All is not lost, because

The best "plan", indexed by the length of the last move, is indeed assembled by the best plan, indexed by the length of the last move. 

Solution:

The last observation above directly lead to the solution. We already mentioned the case of assembling the new solution when the newly added box match the color of the last box. In case it is not matching, it is possible to have a solution that simply remove it first and get the obvious best solution recursively, but it is also possible that it is removed together with some earlier boxes with the same color. If that's the case, the between the newly added box and the together to remove box must also be solved optimally, that leads to the code below:

Code:

#include "stdafx.h"

// https://leetcode.com/problems/remove-boxes

#include "LEET_REMOVE_BOXES.h"
#include <map>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_REMOVE_BOXES
{
    class Solution
    {
    public:
        int removeBoxes(vector<int>& boxes)
        {
            if (boxes.size() == 0)
            {
                return 0;
            }

            int n = (int)boxes.size();

            vector<vector<vector<pair<int, int>>>> answers;
            vector<vector<int>> best;
            answers.resize(n);
            best.resize(n);
            for (int i = 0; i < n; i++)
            {
                answers[i].resize(n);
                best[i].resize(n);
                for (int j = 0; j < n; j++)
                {
                    best[i][j] = 0;
                }
            }

            for (int i = 0; i < n; i++)
            {
                answers[i][i].push_back(make_pair(1, 1));
                best[i][i] = 1;
            }

            for (int l = 2; l <= n; l++)
            {
                for (int s = 0; s + l - 1 < n; s++)
                {
                    int e = s + l - 1;
                    if (boxes[e] == boxes[e - 1])
                    {
                        for (auto d : answers[s][e - 1])
                        {
                            int len = d.first;
                            int pts = d.second;

                            int new_len = len + 1;
                            int new_pts = pts + 2 * len + 1;
                            answers[s][e].push_back(make_pair(new_len, new_pts));
                            best[s][e] = max(best[s][e], new_pts);
                        }
                    }
                    else
                    {
                        answers[s][e].push_back(make_pair(1, best[s][e - 1] + 1));
                        best[s][e] = best[s][e - 1] + 1;
                        for (int pe = e - 2; pe >= s; pe--)
                        {
                            if (boxes[e] == boxes[pe])
                            {
                                for (auto d : answers[s][pe])
                                {
                                    int len = d.first;
                                    int pts = d.second;

                                    int new_len = len + 1;
                                    int new_pts = best[pe + 1][e - 1] + pts + 2 * len + 1;
                                    answers[s][e].push_back(make_pair(new_len, new_pts));
                                    best[s][e] = max(best[s][e], new_pts);
                                }
                            }
                        }
                    }
                }
            }

            return best[0][n - 1];
        }
    };
};

using namespace _LEET_REMOVE_BOXES;

int LEET_REMOVE_BOXES()
{
    Solution solution;
    int test_array[] = { 1, 3, 2, 2, 2, 3, 4, 3, 1 };
    vector<int> test(test_array, test_array + _countof(test_array));
    cout << solution.removeBoxes(test) << endl;
    return 0;
}

LeetCode OJ - Max Increase to Keep City Skyline

Problem:

Please find the problem here.

Solution:

Obviously, the key constraint to increasing the height is to keep the both skyline unchanged. Therefore, I computed the skylines with one scan, and then with another scan, we can compute the max increase that keep the city skyline!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/max-increase-to-keep-city-skyline

#include "LEET_MAX_INCREASE_TO_KEEP_CITY_SKYLINE.h"
#include <map>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_MAX_INCREASE_TO_KEEP_CITY_SKYLINE
{
    class Solution
    {
    public:
        int maxIncreaseKeepingSkyline(vector<vector<int>>& grid)
        {
            if (grid.size() == 0 || grid[0].size() == 0)
            {
                return 0;
            }
            size_t height = grid.size();
            size_t width = grid[0].size();
            vector<int> skyline_h;
            vector<int> skyline_v;
            skyline_h.resize(width);
            skyline_v.resize(height);
            for (size_t col = 0; col < width; col++)
            {
                skyline_h[col] = 0;
            }
            for (size_t row = 0; row < height; row++)
            {
                skyline_v[row] = 0;
            }
            for (size_t row = 0; row < height; row++)
            {
                for (size_t col = 0; col < width; col++)
                {
                    skyline_v[row] = max(skyline_v[row], grid[row][col]);
                    skyline_h[col] = max(skyline_h[col], grid[row][col]);
                }
            }
            int answer = 0;
            for (size_t row = 0; row < height; row++)
            {
                for (size_t col = 0; col < width; col++)
                {
                    int allowed = min(skyline_v[row], skyline_h[col]);
                    answer += (allowed - grid[row][col]);
                }
            }
            return answer;
        }
    };
};

using namespace _LEET_MAX_INCREASE_TO_KEEP_CITY_SKYLINE;

int LEET_MAX_INCREASE_TO_KEEP_CITY_SKYLINE()
{
    Solution solution;

    int row1[] = { 3, 0, 8, 4 };
    int row2[] = { 2, 4, 5, 7 };
    int row3[] = { 9, 2, 6, 3 };
    int row4[] = { 0, 3, 1, 0 };

    vector<vector<int>> grid;
    grid.push_back(vector<int>(row1, row1 + _countof(row1)));
    grid.push_back(vector<int>(row2, row2 + _countof(row2)));
    grid.push_back(vector<int>(row3, row3 + _countof(row3)));
    grid.push_back(vector<int>(row4, row4 + _countof(row4)));
    cout << solution.maxIncreaseKeepingSkyline(grid) << endl;
    return 0;
}