Image for post
Image for post
Photo by Sigmund on Unsplash

Today’s problem is an easy tagged question on leetcode. Let us look into the question.

217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

One of the easiest ways to solve this problem is by sorting. Using the sorting function, we can sort our array. After sorting, we can check if any of the adjacent elements are equal. …


Image for post
Image for post
Photo by Nick Fewings on Unsplash

Today’s question is somewhat easy. I thought since we were learning dynamic programming for quite some time, It was good to have a change and learn something easy. Let us look into the question.

412. Fizz Buzz

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three, it should output “Fizz” instead of the number, and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:

n = 15,Return:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"…

Image for post
Image for post
Photo by David Dvořáček on Unsplash

We have been working on dynamic programming for quite some time. Today let us work on some other type of problem. Today’s question is an easy tagged question in Leetcode.

1346. Check If N and Its Double Exist

Given an array arr of integers, check if there exist two integers N and M such that N is the double of M ( i.e. N = 2 * M).

More formally check if there exist two indices i and j such that :

  • i != j
  • 0 <= i, j < arr.length
  • arr[i] == 2 * arr[j]

Example 1:

Input: arr = [10,2,5,3]
Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5. …


Image for post
Image for post
Photo by davide ragusa on Unsplash

Today’s article is the final part of the three-part series of Longest Common Subsequence(LCS) problem. You can follow this link if you need to understand how to solve the LCS problem using top-down.

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). …


Image for post
Image for post
Photo by Les Anderson on Unsplash

Today’s article is the second part of the three-part series of Longest Common Subsequence(LCS) problem. You can follow this link if you need to understand how to solve the LCS problem using recursion.

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). …


Image for post
Image for post
Photo by Tolga Ulkan on Unsplash

Today’s question is a famous question that is solved using Dynamic Programming. You will find many other questions that are variations of this question. Let us jump into the question without further ado. We will be solving this problem in a 3 part series. Today, we will be solving this problem using recursion.

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). …


Image for post
Image for post
Photo by Simon on Unsplash

Today’s problem is a variation of the Unbounded Knapsack problem. We found the solution to the unbounded knapsack yesterday. In case you need a refresher, do follow this link. The question is pulled from Leetcode and is a medium tagged question. Let us look into the problem.

322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin. …


Image for post
Image for post
Photo by Denisse Leon on Unsplash

Today’s problem is another variation of the Knapsack problem. In the earlier version of the knapsack problem, we had a limited number of items. In the current version of the problem, we have an unlimited number of item counts. Let’s jump into the question.

Unbounded Knapsack (Repetition of items allowed)

Given a knapsack weight W and a set of n items with a certain value val[i] and weight wt[i], we need to calculate the maximum amount that could make up this quantity exactly. This is different from the classical Knapsack problem, here we are allowed to use an unlimited number of instances of an item.
Examples:

Input : W = 100
val[] = {1, 30}
wt[] = {1, 50}
Output : 100
There are many ways to fill knapsack.
1) 2 instances of 50 unit weight item.
2) 100 instances of 1 unit weight item.
3) 1 instance of 50 unit weight item and 50
instances of 1 unit weight items. …

Image for post
Image for post
Photo by Immo Wegmann on Unsplash

Today’s problem is a variation of the Knapsack problem. The question is from leetcode and a “Medium” tagged question. Let us jump right into the question.

494. Target Sum

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make the sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. …

Image for post
Image for post
Photo by Maria Teneva on Unsplash

Today, we will be looking into another Dynamic Programming question. The problem statement is a variation of the Knapsack problem. Let us look into the problem statement. I used Aditya Verma’s video as a reference to solve this problem. I have included the link to his video at the end of the video.

Partition a set into two subsets such that the difference of subset sums is minimum

Given an integer array arr of size N, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum and find the minimum difference

Example 1:

Input: N = 4, arr[] = {1, 6, 11, 5} 
Output: 1
Explanation:
Subset1 = {1, 5, 6}, sum of Subset1 = 12
Subset2 = {11}, sum of Subset2 =…

About

Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store