Best time to buy sell stock
You are given an array with the price of the stock on the ith day. You need to max the profit by choosing a day to buy and choosing different day to sell the stock The solution for this problem is straight forward. We take 2 variables i.e minPrice and maxProfit. minPrice will have the […]
Given a triangle, find the minimum path sum from top to bottom.
Given a triangle, find the minimum path sum from top to bottom. In each step you can only move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + […]
Check if the given board is valid Sudoku or not explanation with solution in CPP
Determine if a 9×9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: 1. Each row must contain the digits 1-9 without repetition. 2. Each column must contain the digits 1-9 without repetition. 3. Each of the 9 3×3 sub-boxes of the grid must contain the digits […]
Pascal’s triangle 2
Before solving this, have a look at similar problem “pascal’s triangle”. Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle. The only difference between this and the previous question is, we need to use o(k) space. We follow the same procedure, but instead of using a 2D vector, we use 1D […]
Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.
n Pascal’s triangle, each number is the sum of the two numbers directly above it. Example: Input: 5 Output: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] Solution analysis: In each row, the first and last element are 1. And the other element is the sum of the two elements in the previous row. e.g. 1 […]
Insert Interval
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] Example 2: Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the […]
Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: “25525511135” Output: [“255.255.11.135”, “255.255.111.35”] The solution for this problem can be done in 2 ways. 1. Iterative/Brute force approach 2. Recursive/DFS But before we solve this, we need to consider below few points: An IP address consists […]
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list. Example: Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL Reverse Linked List iterative and recursive in C++ To solve this problem we need to use 4 pointers. Below are the 4 pointers are used: 1. new_head- track head position (new_head.next = head) […]
Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping: ‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. Example 1: Input: “12” Output: 2 Explanation: It could be decoded as “AB” (1 […]
check if the given string is valid or not explanation with solution
Validate if a given string is numeric. Some examples: “0” => true ” 0.1 ” => true “abc” => false “1 a” => false “2e10” => true Below is the list of characters that can be in a valid decimal number: • Numbers 0-9 • Exponent – “e” • Positive/negative sign – “+”/”-” • Decimal […]