Problem

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution 1: Brute Force

Time complexity: O(nk)

Space complexity: O(1)

C++

// Author: Huahua, 420 ms

class Solution {

public:

ListNode* mergeKLists(vector<ListNode*>& lists) {

ListNode dummy(0);

ListNode *cur = &dummy;

while (true) {

ListNode** min_head = nullptr;

for (auto& head : lists) {

if (!head) continue;

if (!min_head || head->val < (*min_head)->val)

min_head = &head;

}

if (!min_head) break;

cur->next = new ListNode((*min_head)->val);

cur = cur->next;

*min_head = (*min_head)->next;

}

return dummy.next;

}

};

Solution 2: Heap / Priority Queue

Time complexity: O(nlogk)

Space complexity: O(k)

C++

// Author: Huahua, 16 ms (<99.88%)

class Solution {

public:

ListNode* mergeKLists(vector<ListNode*>& lists) {

ListNode dummy(0);

ListNode *cur = &dummy;

auto comp = [](ListNode* a, ListNode* b) { return a->val > b->val; };

priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> q(comp);

for (ListNode* list : lists)

if (list) q.push(list);

while (!q.empty()) {

cur->next = q.top(); q.pop();

cur = cur->next;

if (cur->next) q.push(cur->next);

}

return dummy.next;

}

};

Problem

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Solution: Stack

Using a stack to track the existing open parentheses, if the current one is a close parenthesis but does not match the top of the stack, return false, otherwise pop the stack. Check whether the stack is empty in the end.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 0 ms

class Solution {

public:

bool isValid(string s) {

map<char, char> p{{')', '('}, {']', '['}, {'}', '{'}};

stack<char> st;

for (char c : s) {

if (!p.count(c)) {

st.push(c);

} else {

if (st.empty() || p[c] != st.top()) return false;

st.pop();

}

return st.empty();

}

};

Python3

# Author: Huahua

class Solution:

def isValid(self, s):

p = {')' : '(', ']': '[', '}' : '{'}

stack = []

for c in s:

if c not in p:

stack.append(c)

else:

if not stack or stack[-1] != p[c]: return False

stack.pop()

return not stack

Posts published in October 2018

花花酱 LeetCode 20. Valid Parentheses

Problem

Solution: Stack

C++

Python3

Related Problems

Posts published in October 2018

花花酱 LeetCode 23. Merge k Sorted Lists

Problem

Solution 1: Brute Force

C++

Solution 2: Heap / Priority Queue

C++

花花酱 LeetCode 20. Valid Parentheses

Problem

Solution: Stack

C++

Python3

Related Problems