Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Some Examples
2.
Approach
2.1.
Pseudocode
3.
Implementation in C++
3.1.
Complexity Analysis
4.
Frequently asked questions
5.
Key takeaways
Last Updated: Mar 27, 2024

Longest subsequence such that the difference between adjacent elements is K

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

This blog will discuss the solution to this problem to find the Longest subsequence such that the difference between adjacent elements is K.For example consider this array[] = {2, 5, 7, 5, 3, 0, 1}, K =2 here the longest subsequence with the difference between adjacent equal to K is [5, 7, 5, 3, 1]. 

Problem Statement

We are given an array arr[] of size N, and our task is to find the longest subsequence such that the absolute difference between adjacent elements in K. So before we deep dive into the answer, we should look at some examples to understand the problem better.

Some Examples

Example 1:

Input:

arr[] =  [1, 3, 1, 5, 4], K = 2

 

Output: 

3

 

Explanation:

The longest subsequence with the difference between the adjacent elements as 2 is [1, 3, 1] 

 

Example 2:

Input:

arr[] = [2, 7, 4, 5, 1, 4, 9]   K = 3

 

Output:

4 

Approach

  • To solve this problem, to find the longest subsequence such that the difference between adjacent elements is K, we will use dynamic programming.
  • We will store the length of the longest subsequence, which has a difference K between the adjacent elements after including the current element.
  • We will create an unordered map m where m[i] will represent the maximum length of the subsequence, which includes the integer i.
  • The relation to finding the maximum length subsequence is given below:

m[i] = 1 + max(m[i – K], m[i + K])

  • We will store the max value of m[i] in another variable named ans and when the loop is over we will return the variable.

Pseudocode

int longestSubsequenceInArray(vector<int> &arr, int K){
  unordered_map<int, int> m;
    int ans = 1;
    for (auto x: arr)
    {
        m[x] = 1;
        m[x] = 1 + max(m[x + K], m[x - K]);
        ans = max(ans, m[x]);
    }
    return ans;
}
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Implementation in C++

// C++ code to find the Longest subsequence such that the difference between adjacent elements is K
#include <bits/stdc++.h>
using namespace std;

// function to find the longest subsequence such that the
// difference between adjacent elements of array is K
int longestSubsequenceInArray(vector<int> &arr, int K)
{
    // to store the length of longest subsequence
    unordered_map<int, int> m;

    // to store the answer
    int ans = 1;

    for (auto x: arr)
    {
        m[x] = 1;

        // taking the maximum of x+Kth element and x-Kth element
        m[x] = 1 + max(m[x + K], m[x - K]);

        ans = max(ans, m[x]);
    }

    // return the answer
    return ans;
}

// Driver Code to find the Longest subsequence such that the difference between adjacent elements is K
int main()
{
    vector<int> arr = {1, 4, 7, 5, 6, 10, 3};
    int K = 3;

    cout << longestSubsequenceInArray(arr, K);
}

 

Output:

Input: N = 7 , K = 3
 { 1, 4, 7, 5, 6, 10, 3 }

Output: 4

 

Complexity Analysis

Time Complexity: O(N)

Since we are doing single traversals, therefore, the time complexity is O(N).

Space Complexity: O(N)

Since we store our answer in a map, the space complexity will be O(N).

Check out this : Longest common subsequence

Frequently asked questions

Q1. What is a Subsequence?

Ans. A subsequence is a sequence that can be derived from a sequence by deleting some elements of that sequence, but the order remains unchanged.

 

Q2. What is an application of recursion?

Ans. Many well-known sorting algorithms (Quick sort, Merge sort, etc.) use recursion.

 

Q3. What is a heap?

Ans. Heap is a tree-based data structure. More precisely, it is a particular case of a balanced binary tree that stores the tree’s nodes in a specific order. 

Key takeaways

In this article, we discussed the problem to find the longest subsequence such that the difference between adjacent elements is K. We have discussed its approach based on the priority queue, and we have also discussed the time and space complexities of the approach.

We hope you have understood the problem and now it is your turn to code this problem and other similar problems such as Minimum Subset Sum Difference in your own way.

Until then, Keep Learning and Keep Coding.


Previous article
Check if a path exists from start to end cell in given Matrix with obstacles in at most K moves
Next article
Inclusion-Exclusion Principle
Live masterclass