Wildcard Matching
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’. ‘?’ Matches any single character. ‘*’ Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). Note: s could be empty and contains only lowercase letters a-z. […]
Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order in C++
Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] Before looking into the solution, I recommend you to please go through print matrix in spiral order solution. These two solutions are very similar. Given a matrix of m x n elements (m rows, n […]
Reverse Linked List iterative and recursive in C++
Example: Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL This problem can be solved in 2 ways. 1. Iterative 2. Recursive. 1. Iterative solution. In this solution, we need 3 pointers. In this solution, we need 3 pointers. And initialize as shown below: prev = NULL Curr = head Temp = NULL So we iterate and reverse the […]
Merge Intervals in C++
Given a collection of intervals, merge all overlapping intervals. Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]. Example 2: Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping. This problem can be solved in 2 ways: 1. Brute force approach 2. By sorting […]
Given an array of non-negative integers determine if you are able to reach the last index in C++
Explanation: Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example 1: Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to […]
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1: Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5] The Solution is very simple. As shown in the image above, 1. We traverse right 2. We traverse down 3. We traverse left 4. We traverse up To achieve this, we take 4 […]
Implement pow(x, n), which calculates x raised to the power n (xn) in C++
Example 1: Input: 2.00000, 10 Output: 1024.00000 Example 2: Input: 2.10000, 3 Output: 9.26100 Example 3: Input: 2.00000, -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 Achieve it with in O(long n) This problem can be solved in 4 different ways: 1. Recursive 2. Iterative 3. Divide and Conquer 4. Bit Manipulation […]
Rain water trapping
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Before solving this problem, please take a look at “Container with most water” problem. There I have explained in detail on how two pointers […]
Group Anagrams in C++
Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"] Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] • All inputs will be in lowercase. • The order of your output does not matter. This problem can be solved easily using Maps. Solution involves 2 steps: 1. Sort the element and […]
You are given an n x n 2D matrix rotate it by 90 degrees (clockwise) in C++.
Note: You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. Example 1: Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ], rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,2], [9,6,3] ] We […]