Problem No.
26
Remove Duplicates from Sorted Array
Statement:
Given an integer array nums sorted in non-decreasing order, remove
the duplicates in-place such that each unique element appears
only once. The relative order of the elements should be kept the same.
Code:
int removeDuplicates(int* nums, int numsSize) {
if (numsSize == 0)
return 0;
int i = 0;
for (int j = 1; j < numsSize; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
Time Complexity: O(n)
Space Complexity: O(1)
Problem No. 83
Remove Duplicates from Sorted List
Statement:
Given the head of a sorted linked list, delete all duplicates such that each
element appears only once. Return the linked list sorted as well.
Code:
struct ListNode* deleteDuplicates(struct ListNode* head) {
if (head == NULL)
return NULL;
struct ListNode *current = head;
while (current != NULL && current->next != NULL) {
if (current->val == current->next->val) {
struct ListNode *temp = current->next;
current->next = current->next->next;
free(temp);
}
else {
current = current->next;
}
}
return head;
}
Time Complexity: O(n)
Space Complexity: O(1)
Problem No. 141
Linked List Cycle
Statement:
Given head, the head of a linked list, determine if the linked list has a
cycle in it. There is a cycle in a linked list if there is some node in the list
that can be reached again by continuously following the next pointer.
Internally, pos is used to denote the index of the node
that tail's next pointer is connected to. Note that pos is not passed as a
parameter. Return true if there is a cycle in the linked list. Otherwise,
return false.
Code:
bool hasCycle(struct ListNode *head) {
struct ListNode *slow = head;
struct ListNode *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}
Time Complexity: O(n)
Space Complexity: O(1)
Problem No. 19
Remove Nth Node from End of List
Statement:
Given the head of a linked list, remove the nth node from the end of the list
and return its head.
Code:
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode dummy;
[Link] = head;
struct ListNode *fast = &dummy;
struct ListNode *slow = &dummy;
for (int i = 0; i <= n; i++) {
fast = fast->next;
}
while (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
struct ListNode *temp = slow->next;
slow->next = slow->next->next;
free(temp);
return [Link];
}
Time Complexity: O(n)
Space Complexity: O(1)
Problem No. 20
Valid Parentheses
Statement:
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']',
determine if the input string is valid.
An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same
type
Code:
class Solution {
public boolean isValid(String s) {
Map<Character, Character> map = new HashMap<>();
[Link](')', '(');
[Link]('}', '{');
[Link](']', '[');
Stack<Character> stack = new Stack<>();
for (char c : [Link]()) {
if ([Link](c)) {
[Link](c);
} else if ([Link](c)) {
if ([Link]() || [Link](c) != [Link]()) {
return false;
}
}
}
return [Link]();
Time Complexity: O(n)
Space Complexity: O(n)
Problem No. 443
String Compression
Statement:
Given an array of characters chars, compress it using the following
algorithm:
Begin with an empty string s. For each group of consecutive repeating
characters in chars:
If the group's length is 1, append the character to s.
Otherwise, append the character followed by the group's length.
Code:
class Solution {
public:
int compress(vector<char>& chars) {
int i = 0, idx = 0;
while (i < [Link]()) {
char c = chars[i];
int cnt = 0;
while (i < [Link]() && chars[i] == c) {
i++;
cnt++;
}
chars[idx++] = c;
if (cnt > 1) {
string s = to_string(cnt);
for (char ch : s)
chars[idx++] = ch;
}
}
return idx;
Time Complexity: O(n) Space Complexity: O(1)
Problem No. 88
Merge Sorted Array
Statement:
You are given two integer arrays nums1 and nums2, sorted in non-
decreasing order, and two integers m and n, representing the number of
elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing
order.
Code:
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j])
nums1[k--] = nums1[i--];
else
nums1[k--] = nums2[j--];
}
}
};
Time Complexity: O(m+n)
Space Complexity: O(1)
Problem No. 53
Maximum Subarray
Statement:
Given an integer array nums, find the subarray with the largest sum, and
return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Code:
class Solution {
public int maxSubArray(int[] nums) {
int currSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < [Link]; i++) {
currSum = [Link](nums[i], currSum + nums[i]);
maxSum = [Link](maxSum, currSum);
}
return maxSum;
}
Time Complexity: O(n)
Space Complexity: O(1)
Problem No. 150
Evaluate Reverse Polish Notation
Statement:
You are given an array of strings tokens that represents an arithmetic
expression in a Reverse Polish Notation.
Evaluate the expression. Return an integer that represents the value of
the expression.
Code:
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for (string &t : tokens) {
if (t == "+" || t == "-" || t == "*" || t == "/") {
int b = [Link](); [Link]();
int a = [Link](); [Link]();
if (t == "+") [Link](a + b);
else if (t == "-") [Link](a - b);
else if (t == "*") [Link](a * b);
else [Link](a / b);
} else {
[Link](stoi(t));
}
}
return [Link]();
}
};
Time Complexity: O(n) Space Complexity: o(n)
Problem No. 9
Palindrome Number
Statement:
Given an integer x, return true if x is a palindrome, and false otherwise.
Code:
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) return false;
int rev = 0;
while (x > rev) {
rev = rev * 10 + x % 10;
x /= 10;
}
return x == rev || x == rev / 10;
}
};
Time Complexity: O(log₁₀ n)
Space Complexity: O(1)
Problem No. 125
Valid Palindrome
Statement:
A phrase is a palindrome if, after converting all uppercase letters into
lowercase letters and removing all non-alphanumeric characters, it reads
the same forward and backward. Alphanumeric characters include letters
and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Code:
class Solution {
public:
bool isPalindrome(string s) {
int i = 0, j = [Link]() - 1;
while (i < j) {
while (i < j && !isalnum(s[i])) i++;
while (i < j && !isalnum(s[j])) j--;
if (tolower(s[i]) != tolower(s[j]))
return false;
i++;
j--;
}
return true;
}
};
Time Complexity: O(n)
Space Complexity: O(1)
Problem No. 876
Middle of the Linked List
Statement:
Given the head of a singly linked list, return the middle node of the linked
list.
If there are two middle nodes, return the second middle node.
Code:
class Solution {
public ListNode middleNode(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && [Link] != null) {
slow = [Link];
fast = [Link];
}
return slow;
}
Time Complexity: O(n) Space
Complexity: O(1)
Problem No. 4
Median of Two Sorted Arrays
Statement:
Given two sorted arrays nums1 and nums2 of size m and n respectively,
return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Code:
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>&
nums2) {
if ([Link]() > [Link]())
return findMedianSortedArrays(nums2, nums1);
int m = [Link](), n = [Link]();
int low = 0, high = m;
while (low <= high) {
int cut1 = (low + high) / 2;
int cut2 = (m + n + 1) / 2 - cut1;
int l1 = (cut1 == 0) ? INT_MIN : nums1[cut1 - 1];
int l2 = (cut2 == 0) ? INT_MIN : nums2[cut2 - 1];
int r1 = (cut1 == m) ? INT_MAX : nums1[cut1];
int r2 = (cut2 == n) ? INT_MAX : nums2[cut2];
if (l1 <= r2 && l2 <= r1) {
if ((m + n) % 2 == 0)
return (max(l1, l2) + min(r1, r2)) / 2.0;
return max(l1, l2);
}
else if (l1 > r2)
high = cut1 - 1;
else
low = cut1 + 1;
}
return 0.0;
}
};
Time Complexity: O(log(min(m, n)))
Space Complexity: O(1)
Problem No. 206
Reverse Linked List
Statement:
Given the head of a singly linked list, reverse the list, and return the
reversed list.
Code:
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* curr = head;
struct ListNode* next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
Time Complexity: O(n)
Space Complexity: O(1)
Problem No. 189
Rotate Array
Statement:
Given an integer array nums, rotate the array to the right by k steps,
where k is non-negative.
Code:
class Solution {
public:
void reverse(vector<int>& nums, int l, int r) {
while (l < r)
swap(nums[l++], nums[r--]);
}
void rotate(vector<int>& nums, int k) {
int n = [Link]();
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
};
Time Complexity: O(n)
Space Complexity: O(1)
Problem No. 242
Valid Anagram
Statement:
Given two strings s and t, return true if t is an anagram of s,
and false otherwise.
Code:
class Solution {
public:
bool isAnagram(string s, string t) {
if ([Link]() != [Link]()) return false;
int cnt[26] = {0};
for (char c : s) cnt[c - 'a']++;
for (char c : t)
if (--cnt[c - 'a'] < 0) return false;
return true;
}
};
Time Complexity: O(n)
Space Complexity: O(1)
Problem No. 92
Reverse Linked List II
Statement:
Given the head of a singly linked list and two
integers left and right where left <= right, reverse the nodes of the list
from position left to position right, and return the reversed list.
Code:
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (!head || left == right) return head;
ListNode dummy(0);
[Link] = head;
ListNode* prev = &dummy;
for (int i = 1; i < left; i++)
prev = prev->next;
ListNode* curr = prev->next;
for (int i = 0; i < right - left; i++) {
ListNode* temp = curr->next;
curr->next = temp->next;
temp->next = prev->next;
prev->next = temp;
}
return [Link];
}
};
Time Complexity: O(n) Space Complexity:
O(1)
Problem No. 169
Majority Element
Statement:
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times.
You may assume that the majority element always exists in the array.
Code:
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = 0, count = 0;
for (int num : nums) {
if (count == 0)
candidate = num;
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
};
Time Complexity: O(n)
Space Complexity: O(1)
Problem No. 232
Implement Queue using Stacks
Statement:
Implement a first in first out (FIFO) queue using only two stacks. The
implemented queue should support all the functions of a normal queue
(push, peek, pop, and empty).
Implement the MyQueue class:
void push(int x) Pushes element x to the back of the queue.
int pop() Removes the element from the front of the queue and
returns it.
int peek() Returns the element at the front of the queue.
boolean empty() Returns true if the queue is empty, false otherwise.
Code:
class MyQueue {
stack<int> in, out;
public:
MyQueue() {}
void push(int x) {
[Link](x);
}
int pop() {
peek();
int x = [Link]();
[Link]();
return x;
}
int peek() {
if ([Link]()) {
while (![Link]()) {
[Link]([Link]());
[Link]();
}
}
return [Link]();
}
bool empty() {
return [Link]() && [Link]();
}
};
Time Complexity:
push() → O(1)
pop() → O(1) amortized
peek() → O(1) amortized
empty() → O(1)
Space Complexity: O(n)
Problem No. 225
Implement Stack Using Queues
Statement:
Implement a last-in-first-out (LIFO) stack using only two queues. The
implemented stack should support all the functions of a normal stack
(push, top, pop, and empty).
Implement the MyStack class:
void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns
it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.
Code:
class MyStack {
queue<int> q;
public:
MyStack() {}
void push(int x) {
[Link](x);
for (int i = 0; i < [Link]() - 1; i++) {
[Link]([Link]());
[Link]();
}
}
int pop() {
int x = [Link]();
[Link]();
return x;
}
int top() {
return [Link]();
}
bool empty() {
return [Link]();
}
};
Time Complexity:
push() → O(n)
pop() → O(1)
top() → O(1)
empty() → O(1)
Space Complexity: O(n)
Problem No. 3
Longest Substring Without Repeating
Statement:
Given a string s, find the length of the longest substring without
duplicate characters.
Code:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> last(256, -1);
int ans = 0, left = 0;
for (int right = 0; right < [Link](); right++) {
left = max(left, last[s[right]] + 1);
last[s[right]] = right;
ans = max(ans, right - left + 1);
}
return ans;
}
};
Time Complexity: O(n)
Space Complexity: O(1)